# My Weblog

## Project Euler Problem 153

Project euler problem 153 is one the best problem which i solved on Project Euler.I tried this problem in 2007 and could not solved.Once you spot the pattern its rather easy to solve.
1—->1
2—->1,1+i,1-i,2
3—->1,3
4—->1,1-i,1+i,2,2+2I,2-2I,4
5—->1,1+2i,1-2i,2+i,2-i,5
6—->1,1+i,1-i,2,3,3+3i,3-3i,6
7—->1,7
8—->1,1+i,1-i,2,2+2i,2-2i,4,4+4i,4-4i,8
9—->1,3,9
10—> 1,1+i,1-i,2,2+2i,2-2i,5,1+2i,1-2i,2+i,2-i,2+4i,2-4i,4+2i,4-2i,1+3i,1-3i,3+i,3-i
If you notice that 1+i and 1-i are divisors of all the numbers which are multiple of 2. 2+2i and 2-2i is divisors of all the number which are multiple of 4. 1+2i is divisor of all the numbers multiple of 5. Also out of these all the divisors only 1+i ,1-i, 1+2i,1-2i,2+i,2-i,1+3i,1-3i,3+i and 3-i are primitive solutions and rest can be derived from these solutions so i wrote brute force to test this algorithm.

```#include<cstdio>
#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
#define Lim 100000
typedef pair<int,int> PI;
multimap<int,int> M;
int real[Lim+1],ima[Lim+1];

int main()
{
long long sum=0;
for(int i=1;i<=Lim;i++) for(int j=i;j<=Lim;j+=i) real[j]+=i;
for(int a=1;a*a<=Lim;a++)
for(int b=1;b<=a;b++) if(__gcd(a,b)==1)M.insert(PI(a*a+b*b,(a==b)?(a+b):2*(a+b)));

for(multimap<int,int>:: iterator it=M.begin();it!=M.end();it++)
{
int i=(*it).first,val=(*it).second;
for(int j=1;i*j<=Lim;j++)
for(int k=i*j;k<=Lim;k+=i*j) ima[k]+=j*val;
}

for(int i=1;i<=Lim;i++) sum+=real[i]+ima[i];
cout<<sum<<endl;
}
```

But for 10^8, its not going work because this code heavily depends on memory. For this problem we don’t need any array and map. Here is source code which i derived for previous code.

```#include<cstdio>
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#define Lim 100000000
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PI;

multimap<ll,ll> M;
int main()
{
ll sum=0;
for(int i=1;i<=Lim;i++)
{
sum+=(Lim/i)*i;

}

for(int a=1;a*a<Lim;a++)
for(int b=1;b<=a /*&& (a*a+b*b)<=Lim*/;b++)
if(__gcd(a,b)==1)
{
int i=(a*a+b*b),val=(a==b)?(a+b):2*(a+b);
for(int j=1;i*j<=Lim;j++)
{
sum+=(j*val*(Lim/(i*j)));
}
}

cout<<sum<<endl;
}
```

149th problem. One more to go to next level.