My Weblog

Blog about programming and math

Project Euler 271

Nice problem and better understanding of CRT. I simply use the algorithm Quadratic residue given on wiki section “Complexity of finding square roots”. For example case 91, we factor it into 7*13.x^3=1(mod 7) which is (1,2,4) and x^3=1(mod 13) which is (1,3,9).Now the trick is simply to combine these results using CRT.
Use the chinese remainder theorem on *each pair* of solutions.
The pair x=1 (mod 7), x=1 (mod 13) gives you x=1 (mod 91).
The pair x=1 (mod 7), x=3 (mod 13) gives you x=29 (mod 91).
The pair x=1 (mod 7), x=9 (mod 13) gives you x=22 (mod 91)
The pair x=2 (mod 7), x=1 (mod 13) gives you x=79 (mod 91).
The pair x=2 (mod 7), x=3 (mod 13) gives you x=16 (mod 91).
The pair x=2 (mod 7), x=9 (mod 13) gives you x=9 (mod 91).
The pair x=4 (mod 7), x=1 (mod 13) gives you x=53 (mod 91)
The pair x=4 (mod 7), x=3 (mod 13) gives you x=81 (mod 91).
The pair x=4 (mod 7), x=9 (mod 13) gives you x=74 (mod 91). As problem does not require 1.
Here is my source code and it really took time to implement and solve this problem so I am thinking to solve earlier easy problem 🙂 and get into the next level.

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
typedef pair<long long ,long long> PL;
long long p[14]={2,3,5,7,11,13,17,19,23,29,31,37,41,43};
vector<long long > v[14];
vector<PL> T;
long long M=13082761331670030LL;
long long sum=0;
int n=14;
long long GCD(long long a,long long b)
	{

		long long x = 0 ,lastx = 1,y = 1 ,lasty = 0;
		long long q,temp;
    		while(b!=0)
		{
        		q = a/b;
        
        		temp = b;
        		b= a % b;
        		a = temp;
        
        		temp = x;
        		x = lastx-q*x;
        		lastx = temp;
        
        		temp = y;
        		y = lasty-q*y;
        		lasty = temp;
		}
    		return  lasty;
	}


			


void Calchines(int lev)
	{
		//cout<<"lev= "<<lev<<endl;
		if(lev==14)
		 {
			long long l=0;
			for(int i=0;i<T.size();i++)
			{
			    long long c=M/T[i].second;
				l+=T[i].first*c*GCD(T[i].second,c);
	
			}
			//cout<<l<<endl;
			while(l<0) l+=M;
			while(l>=M) l-=M;
			sum+=l;
			//cout<<endl<<endl;
		 	return;
		 } 
		for(int i=0;i<v[lev].size();i++)
		 {
			T.push_back(PL(v[lev][i],p[lev]));
			Calchines(lev+1);
			T.erase(T.end());
		 }
	}
	
int main()
	{
		for(int i=0;i<n;i++)
		 {
			for(long long j=1;j<=p[i];j++) if((j*j*j)%p[i]==1) v[i].push_back(j);

		 }
		
		for(int i=0;i<v[0].size();i++)
		{
			T.push_back(PL(v[0][i],p[0]));
			Calchines(1);
			T.erase(T.end());
		}
		cout<<"sum= "<<sum-1<<endl;
	}
			

The next one 272 is more challenging.

Advertisements

March 24, 2010 - Posted by | Programming

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: