Number Theory – Page 3 – Live with passion

836

Asif NaeemFebruary 7, 2015

This problem also can be solved using Dynamic Programming.

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>

using namespace std;

string *str = new string [50];
int N;

int kaadanealgo(int a,int b)
{
	int line[50];
	int max_end_here=0;
	int max_so_far=0;

	for(int i=0;i<N;i++)
	{
		line[i] = 0;
		for(int j=a;j<=b;j++)
		{
			if(str[j][i]=='0')
				line[i]+=-1000000;
			else
				line[i]+=(str[j][i]-'0');
		}
	}


	for(int i=0;i<N;i++)
	{
		max_end_here+=line[i];

		if(max_end_here<0)
		max_end_here = 0;

		if(max_end_here>max_so_far)
			max_so_far = max_end_here;
	}

	return max_so_far;
}
int main()
{
	int t,m,mx;
	string s,a;
	bool c =false;
	cin>>t;
	getchar();

	while(t--)
	{
		getline(cin,s);

		getline(cin,s);
		N = s.size();

		int ind=0;
		str[0] = s;
		for(ind =1;ind<N;ind++)
		{
			getline(cin,s);
			str[ind]=s;
		}
		//N = str[0].size();
		mx = 0;
		for(int i=0;i<ind;i++)
		{
			for(int j=i;j<ind;j++)
			{
				m = kaadanealgo(i,j);
				if(m>mx)
				mx = m;
			}
		}

		cout<<mx<<"\n";
		if(t)
		cout<<"\n";
	}

	return 0;
}

#include <iostream>

#include <string>

#include <cstring>

#include <cstdio>

using namespace std;

string *str = new string [50];

int N;

int kaadanealgo(int a,int b)

{

int line[50];

int max_end_here=0;

int max_so_far=0;

for(int i=0;i<N;i++)

{

line[i] = 0;

for(int j=a;j<=b;j++)

{

if(str[j][i]=='0')

line[i]+=-1000000;

else

line[i]+=(str[j][i]-'0');

}

for(int i=0;i<N;i++)

{

max_end_here+=line[i];

if(max_end_here<0)

max_end_here = 0;

if(max_end_here>max_so_far)

max_so_far = max_end_here;

}

return max_so_far;

}

int main()

{

int t,m,mx;

string s,a;

bool c =false;

cin>>t;

getchar();

while(t--)

{

getline(cin,s);

N = s.size();

int ind=0;

str[0] = s;

for(ind =1;ind<N;ind++)

{

getline(cin,s);

str[ind]=s;

}

//N = str[0].size();

mx = 0;

for(int i=0;i<ind;i++)

{

for(int j=i;j<ind;j++)

{

m = kaadanealgo(i,j);

if(m>mx)

mx = m;

}

cout<<mx<<"\n";

if(t)

cout<<"\n";

}

return 0;

}

Similar problems are : uva 108, uva 10074,uva 10667; These can be solved using the same algorithm.

Theory: We know that, From 0-9, each digit occurs once From 0-99, each digit occurs 20 times (10x in position 1 and 10x in position 2) From 0-999, each digit occurs 300 times (100x in P1, 100x in P2, 100x in P3) If the range is from 0 to a power of 10 then occurrence

Continue Reading “12241” →

12542

Asif NaeemNovember 19, 2014

#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
#include <math.h>
#include <vector>

#define SZ 100005

using namespace std;

int prim[SZ];
vector<int> v;

void primgen()
{
	v.push_back(2);
	prim[2]=0;
	for(int i=3;i<SZ;i+=2)
	{
		if(prim[i]==0)
		{
			v.push_back(i);
			for(int j=i*3;j<SZ;j+=i)
			prim[j]=1;
		}
	}

	//cout<<v.size()<<"\n";
}

int main()
{
	int mult[5];
	int m,max_;
	string s;
	primgen();

	while(cin>>s)
	{
		if(s=="0")
		break;
		memset(mult,0,sizeof(mult));
		max_=0;
		m=0;
		for(int j=0;j<s.size();j++)
		{
			m=0;
			//max_=0;
			for(int k=j;k<j+5;k++)
			{
				if(k==s.size())
				break;
				m*=10;
				m+=(s[k]-'0');

				if(m==2 || (prim[m]==0 && m%2==1))
				{
					if(m>max_)
					max_=m;
				}
			}
		}//
		cout<<max_<<"\n";
	}

	return 0;
}

#include <stdio.h>

#include <string.h>

#include <string>

#include <iostream>

#include <math.h>

#include <vector>

#define SZ 100005

using namespace std;

int prim[SZ];

vector<int> v;

void primgen()

{

v.push_back(2);

prim[2]=0;

for(int i=3;i<SZ;i+=2)

{

if(prim[i]==0)

{

v.push_back(i);

for(int j=i*3;j<SZ;j+=i)

prim[j]=1;

}

//cout<<v.size()<<"\n";

}

int main()

{

int mult[5];

int m,max_;

string s;

primgen();

while(cin>>s)

{

if(s=="0")

break;

memset(mult,0,sizeof(mult));

max_=0;

m=0;

for(int j=0;j<s.size();j++)

{

m=0;

//max_=0;

for(int k=j;k<j+5;k++)

{

if(k==s.size())

break;

m*=10;

m+=(s[k]-'0');

if(m==2 || (prim[m]==0 && m%2==1))

{

if(m>max_)

max_=m;

}

}//

cout<<max_<<"\n";

}

return 0;

}

12517

Asif NaeemNovember 18, 2014

Theory: from 0 to 99 there are 2*10^1=20 for each 0 to 9 digits. from 0 to 999 there are 3*10^2=300 for each 0 to 9 digits. so the foemulae is for 0 to n number of 9’s n*10^(n-1) for each 0 to 9 digits. And so, for upto 445 we can find total number

Continue Reading “12517” →

10780

Asif NaeemNovember 16, 2014

#include <iostream>
#include <cstring>
#include <math.h>
#include <stdio.h>
#include <vector>
#include <fstream>

#define ull  unsigned long long

using namespace std;


int factor[10001][1230];
int factorcount[10001][1230];
int prime[10001];
vector<int> v;
ull _MAX;

void primegenerator()
{
	double p=sqrt(10001);

	v.push_back(2);

	for(int i=3;i<p;i+=2)
	{
		if(prime[i]==0)
		for(int j=i*i;j<10001;j+=i)
			prime[j]=1;
	}

	for(int i=3;i<10001;i+=2)
	{
		if(prime[i]==0)
		v.push_back(i);
	}

}

void factorize()
{
	for(int i=2;i<10001;i++)
	{
		int tmp=i;
		int j=0;
		while(tmp>1)
		{
			if(tmp%v[j]==0)
			{
				factorcount[i][j]++;
				factor[i][j]++;
				tmp/=v[j];
				j=-1;

			}
			j++;
			if(j==v.size())
			break;
		}
		for(int k=0;k<1230;k++)
		factorcount[i][k]+=factorcount[i-1][k];

	}
}

int main()
{
	primegenerator();
	factorize();
	int t,m,n;
	int kase=0;
	cin>>t;
	while(t--)
	{
		cin>>m>>n;
		kase+=1;
		if(m<=1 || n<=0)
		{
			cout<<"Case "<<kase<<":\n";
			cout<<"Impossible to divide\n";
			continue;
		}
		int imposbl=0;
		double min_d=2e9;
		for(int i=0;i<1230;i++)
		{
			if(factor[m][i]>factorcount[n][i])
			{
				imposbl=1;
				break;
			}
			else if(factor[m][i] && factorcount[n][i] && factorcount[n][i]/factor[m][i] <min_d)
			{
                 min_d = factorcount[n][i]/factor[m][i];
			}
		}
		cout<<"Case "<<kase<<":\n";
		if(imposbl==1)
		{
           cout<<"Impossible to divide\n";
        }
		else
		{
            cout<<min_d<<"\n";
        }

	}


	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

#include <iostream>

#include <cstring>

#include <math.h>

#include <stdio.h>

#include <vector>

#include <fstream>

#define ull unsigned long long

using namespace std;

int factor[10001][1230];

int factorcount[10001][1230];

int prime[10001];

vector<int> v;

ull _MAX;

void primegenerator()

{

double p=sqrt(10001);

v.push_back(2);

for(int i=3;i<p;i+=2)

{

if(prime[i]==0)

for(int j=i*i;j<10001;j+=i)

prime[j]=1;

}

for(int i=3;i<10001;i+=2)

{

if(prime[i]==0)

v.push_back(i);

}

void factorize()

{

for(int i=2;i<10001;i++)

{

int tmp=i;

int j=0;

while(tmp>1)

{

if(tmp%v[j]==0)

{

factorcount[i][j]++;

factor[i][j]++;

tmp/=v[j];

j=-1;

}

j++;

if(j==v.size())

break;

}

for(int k=0;k<1230;k++)

factorcount[i][k]+=factorcount[i-1][k];

}

int main()

{

primegenerator();

factorize();

int t,m,n;

int kase=0;

cin>>t;

while(t--)

{

cin>>m>>n;

kase+=1;

if(m<=1 || n<=0)

{

cout<<"Case "<<kase<<":\n";

cout<<"Impossible to divide\n";

continue;

}

int imposbl=0;

double min_d=2e9;

for(int i=0;i<1230;i++)

{

if(factor[m][i]>factorcount[n][i])

{

imposbl=1;

break;

}

else if(factor[m][i] && factorcount[n][i] && factorcount[n][i]/factor[m][i] <min_d)

{

min_d = factorcount[n][i]/factor[m][i];

}

cout<<"Case "<<kase<<":\n";

if(imposbl==1)

{

cout<<"Impossible to divide\n";

}

else

{

cout<<min_d<<"\n";

}

return 0;

}

10394

Asif NaeemNovember 16, 2014

#include <iostream>
#include <string>
#include <vector>
#include <math.h>

#define SZ 20000001

using namespace std;

int prime[SZ];
vector<int> v;

struct twin{
	int x;
	int y;
}twinPrime[108001];

void primegen()
{
	double p = sqrt(SZ);

	for(int i=3;i<p;i+=2)
	{
		if(prime[i]==0)
		{
			for(int j=i*i;j<SZ;j+=i)
				prime[j]=1;
		}
	}

	v.push_back(2);
	int cnt=0;
	for(int i=3;i<SZ;i+=2)
	{
		if(prime[i]==0)
		{
			v.push_back(i);
			int t=v.size();
			if(v[t-1]-v[t-2]==2)
			{
				twinPrime[cnt].x = v[t-2];
				twinPrime[cnt].y = v[t-1];
				cnt++;
			}
		}
	}
}


int main()
{
	primegen();
	int size = v.size();
	int n;

	while(cin>>n)
	{
		cout<<"("<<twinPrime[n-1].x<<", "<<twinPrime[n-1].y<<")\n";
	}
	return 0;
}

#include <iostream>

#include <string>

#include <vector>

#include <math.h>

#define SZ 20000001

using namespace std;

int prime[SZ];

vector<int> v;

struct twin{

int x;

int y;

}twinPrime[108001];

void primegen()

{

double p = sqrt(SZ);

for(int i=3;i<p;i+=2)

{

if(prime[i]==0)

{

for(int j=i*i;j<SZ;j+=i)

prime[j]=1;

}

v.push_back(2);

int cnt=0;

for(int i=3;i<SZ;i+=2)

{

if(prime[i]==0)

{

v.push_back(i);

int t=v.size();

if(v[t-1]-v[t-2]==2)

{

twinPrime[cnt].x = v[t-2];

twinPrime[cnt].y = v[t-1];

cnt++;

}

int main()

{

primegen();

int size = v.size();

int n;

while(cin>>n)

{

cout<<"("<<twinPrime[n-1].x<<", "<<twinPrime[n-1].y<<")\n";

}

return 0;

}

11347

Asif NaeemNovember 14, 2014

#include <iostream>
#include <cstring>
#include <math.h>
#include <stdio.h>
#include <vector>

#define ull  unsigned long long
#define max(a,b) a>=b?a:b

using namespace std;

int ans[200];
int prime[1001];
vector<int> v;
ull _MAX;

void primegenerator()
{
	double p=sqrt(1001);

	v.push_back(2);

	for(int i=3;i<p;i+=2)
	{
		if(prime[i]==0)
		for(int j=i*2;j<1001;j+=i)
			prime[j]=1;
	}

	for(int i=3;i<1001;i+=2)
	{
		if(prime[i]==0)
		v.push_back(i);
	}

}

int main()
{
	string s;
	int _max=0;
	int t,cnt,num;
	int kase=1;
	_MAX = 1000000000;
	_MAX *=_MAX;
	primegenerator();
	cout<<v.size()<<"\n";
	cin>>t;

	while(t--)
	{
		cin>>s;
		cnt=0;
		num=0;
		_max=0;
		memset(ans,0,sizeof(ans));
		for(int i=0;i<s.size();i++)
		{
			if(s[i]=='!')
			cnt++;
			else
			{
				num*=10;
				num+=(s[i]-'0');
			}
		}
		//cout<<num<<" "<<cnt<<"\n";
		cout<<"Case "<<kase++<<": ";

		while(num>1)
		{
			int tmp=num;
			int j=0;
			while(tmp>1)
			{
				if(tmp%v[j]==0)
				{
					tmp/=v[j];
					ans[j]++;
					//_max=max(j,_max);

				}
				else
				j++;
			}
			num-=cnt;
		}

		ull res=1;
		int f=1;
		for(int i=0;i<v.size();i++)
		{
			if(ans[i]!=0)
			res*=(ans[i]+1);
			if(res>_MAX)
			{
				f=0;
				break;
			}
		}
		if(f==1)
		cout<<res<<"\n";
		else
		cout<<"Infinity\n";
	}
	return 0;
}

100

101

102

103

104

105

106

107

#include <iostream>

#include <cstring>

#include <math.h>

#include <stdio.h>

#include <vector>

#define ull unsigned long long

#define max(a,b) a>=b?a:b

using namespace std;

int ans[200];

int prime[1001];

vector<int> v;

ull _MAX;

void primegenerator()

{

double p=sqrt(1001);

v.push_back(2);

for(int i=3;i<p;i+=2)

{

if(prime[i]==0)

for(int j=i*2;j<1001;j+=i)

prime[j]=1;

}

for(int i=3;i<1001;i+=2)

{

if(prime[i]==0)

v.push_back(i);

}

int main()

{

string s;

int _max=0;

int t,cnt,num;

int kase=1;

_MAX = 1000000000;

_MAX *=_MAX;

primegenerator();

cout<<v.size()<<"\n";

cin>>t;

while(t--)

{

cin>>s;

cnt=0;

num=0;

_max=0;

memset(ans,0,sizeof(ans));

for(int i=0;i<s.size();i++)

{

if(s[i]=='!')

cnt++;

else

{

num*=10;

num+=(s[i]-'0');

}

//cout<<num<<" "<<cnt<<"\n";

cout<<"Case "<<kase++<<": ";

while(num>1)

{

int tmp=num;

int j=0;

while(tmp>1)

{

if(tmp%v[j]==0)

{

tmp/=v[j];

ans[j]++;

//_max=max(j,_max);

}

else

j++;

}

num-=cnt;

}

ull res=1;

int f=1;

for(int i=0;i<v.size();i++)

{

if(ans[i]!=0)

res*=(ans[i]+1);

if(res>_MAX)

{

f=0;

break;

}

if(f==1)

cout<<res<<"\n";

else

cout<<"Infinity\n";

}

return 0;

}

11415

Asif NaeemNovember 12, 2014

#include <iostream>
#include <math.h>
#include <vector>

#define ull unsigned long long
#define SIZE 2703664
using namespace std;

int prime[1700];//3200
ull factor[SIZE];
int arr[10000001];
vector<int> v;

void primeGenerator()
{
	double p = sqrt(1700);
	for(int i=3;i<p;i+=2)
	{
		if(prime[i]==0)
		{
			for(int j=i+i;j<1700;j+=i)
			prime[j]=1;
		}
	}

	v.push_back(2);

	for(int i=3;i<1700;i+=2)
	{
		if(prime[i]==0)
		v.push_back(i);
	}
}


void countfactor()
{
	int tmp;
	factor[0]=1;

	factor[1]=1;

	factor[2]=1;


	for(int i=3;i<SIZE;i++)
	{
		tmp = i;
		int j=0;
		factor[i]=0;
		while(tmp>=(v[j]*v[j]))
		{
			if(tmp%v[j]==0)
			{
				tmp/=v[j];
				factor[i]++;
				j=-1;
			}
			j++;

			if(j==v.size())
			break;

		}
		if(tmp>1)
		factor[i]++;

		factor[i]+=factor[i-1];


	}

}

int main()
{
	primeGenerator();
	countfactor();

	ull low,mid,high;
	ull n,ans=0;
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n;
		low=0;
		mid=SIZE/2;
		high=SIZE;
		ans = 0;
		if(arr[n])
		{
			cout<<arr[n]<<"\n";
			continue;
		}
		while((high-low)>1)
		{
			if(factor[mid]<=n)
			{
				low=mid;
				mid=(low+high)/2;
				//ans=high;
			}
			else
			{
				high=mid;
				mid=(low+high)/2;
				//ans=low;
			}
		}

		if(factor[mid+1]>n && factor[mid]<=n)
		{
			arr[n]=mid+1;
		}
		cout<<arr[n]<<"\n";
	}

	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

#include <iostream>

#include <math.h>

#include <vector>

#define ull unsigned long long

#define SIZE 2703664

using namespace std;

int prime[1700];//3200

ull factor[SIZE];

int arr[10000001];

vector<int> v;

void primeGenerator()

{

double p = sqrt(1700);

for(int i=3;i<p;i+=2)

{

if(prime[i]==0)

{

for(int j=i+i;j<1700;j+=i)

prime[j]=1;

}

v.push_back(2);

for(int i=3;i<1700;i+=2)

{

if(prime[i]==0)

v.push_back(i);

}

void countfactor()

{

int tmp;

factor[0]=1;

factor[1]=1;

factor[2]=1;

for(int i=3;i<SIZE;i++)

{

tmp = i;

int j=0;

factor[i]=0;

while(tmp>=(v[j]*v[j]))

{

if(tmp%v[j]==0)

{

tmp/=v[j];

factor[i]++;

j=-1;

}

j++;

if(j==v.size())

break;

}

if(tmp>1)

factor[i]++;

factor[i]+=factor[i-1];

}

int main()

{

primeGenerator();

countfactor();

ull low,mid,high;

ull n,ans=0;

int t;

cin>>t;

while(t--)

{

cin>>n;

low=0;

mid=SIZE/2;

high=SIZE;

ans = 0;

if(arr[n])

{

cout<<arr[n]<<"\n";

continue;

}

while((high-low)>1)

{

if(factor[mid]<=n)

{

low=mid;

mid=(low+high)/2;

//ans=high;

}

else

{

high=mid;

mid=(low+high)/2;

//ans=low;

}

if(factor[mid+1]>n && factor[mid]<=n)

{

arr[n]=mid+1;

}

cout<<arr[n]<<"\n";

}

return 0;

}

10856

Asif NaeemNovember 9, 2014

#include <iostream>
#include <string>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <stdlib.h>

#define SIZE 2800001
#define ull unsigned long long

using namespace std;

int prime[1700];
ull arr [SIZE];//[10000001+5];
vector<int> v;

void primeGenerator()
{
	double p = sqrt(1700);
	for(int i=3;i<p;i+=2)
	{
		for(int j=i+i;j<1700;j+=i)
		{
			prime[j]=1;
		}
	}

	v.push_back(2);

	for(int i=3;i<1700;i++)
	{
		if(prime[i]==0 && i%2!=0)
		{
			v.push_back(i);
		}
	}
}

void factorize()
{
	int tmp;
	arr[0]=1;
	arr[1]=0;
	arr[2]=1;
	for(int i=3;i<SIZE;i++)
	{
		tmp = i;
		arr[i]=0;
		int j=0;
		while(tmp>=(v[j]*v[j]))
		{
			if(tmp%v[j]==0)
			{
				tmp/=v[j];
				arr[i]++;
				j=-1;
			}
			j++;

			if(j==v.size())
			break;
		}
		//cout<<tmp<<"\n";
		if(tmp>1)
		 arr[i]++;
		arr[i]+=arr[i-1];
	}
}

int main()
{
	int n,kase=1;
	int mid;
	int high;
	int low;
	for(int i=0;i<1700;i++)
	{
		prime[i]=0;
	}
	primeGenerator();
	factorize();
	while(cin>>n)
	{
		if(n<0)
		break;
		if(n==0)
		{
			cout<<"Case "<<kase++<<": 0!\n";
			continue;

		}
		mid=SIZE/2;
		high=SIZE;
		low=0;

		//binary search
		while((high-low)>1)
		{
			mid=(high+low)/2;
			if(arr[mid]<n)
				low=mid;
			else
				high = mid;

		}
		if(arr[low]==n)
		cout<<"Case "<<kase++<<": "<<low<<"!\n";
		else if(arr[high]==n)
		cout<<"Case "<<kase++<<": "<<high<<"!\n";
		else
		cout<<"Case "<<kase++<<": Not possible.\n";

	}

	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

#include <iostream>

#include <string>

#include <stdio.h>

#include <math.h>

#include <vector>

#include <stdlib.h>

#define SIZE 2800001

#define ull unsigned long long

using namespace std;

int prime[1700];

ull arr [SIZE];//[10000001+5];

vector<int> v;

void primeGenerator()

{

double p = sqrt(1700);

for(int i=3;i<p;i+=2)

{

for(int j=i+i;j<1700;j+=i)

{

prime[j]=1;

}

v.push_back(2);

for(int i=3;i<1700;i++)

{

if(prime[i]==0 && i%2!=0)

{

v.push_back(i);

}

void factorize()

{

int tmp;

arr[0]=1;

arr[1]=0;

arr[2]=1;

for(int i=3;i<SIZE;i++)

{

tmp = i;

arr[i]=0;

int j=0;

while(tmp>=(v[j]*v[j]))

{

if(tmp%v[j]==0)

{

tmp/=v[j];

arr[i]++;

j=-1;

}

j++;

if(j==v.size())

break;

}

//cout<<tmp<<"\n";

if(tmp>1)

arr[i]++;

arr[i]+=arr[i-1];

}

int main()

{

int n,kase=1;

int mid;

int high;

int low;

for(int i=0;i<1700;i++)

{

prime[i]=0;

}

primeGenerator();

factorize();

while(cin>>n)

{

if(n<0)

break;

if(n==0)

{

cout<<"Case "<<kase++<<": 0!\n";

continue;

}

mid=SIZE/2;

high=SIZE;

low=0;

//binary search

while((high-low)>1)

{

mid=(high+low)/2;

if(arr[mid]<n)

low=mid;

else

high = mid;

}

if(arr[low]==n)

cout<<"Case "<<kase++<<": "<<low<<"!\n";

else if(arr[high]==n)

cout<<"Case "<<kase++<<": "<<high<<"!\n";

else

cout<<"Case "<<kase++<<": Not possible.\n";

}

return 0;

}

10139

Asif NaeemNovember 8, 2014

#include <iostream>
#include <math.h>
#include <vector>
#include <map>
#include <sstream>
#include <fstream>

#define SIZE 46500
#define lld long long
using namespace std;

// sqrt of 2^31 is ~46400
vector<int> v;
int prime[SIZE];

void PrimeGenerate()
{
    double p = sqrt(SIZE)+4;

    for(int i=3;i<p;i+=2)
    {
        if(prime[i]==0)
        {
            for(int j=i+i;j<SIZE;j+=i)
            prime[j]=1;

        }
    }
    v.clear();
    v.push_back(2);

    for(int j=3;j<SIZE;j++)
    {
       if(prime[j]==0 && j%2!=0)
       v.push_back(j);
    }

}

int main()
{
  int m,cnt;
  lld a,n;
  map<int,int> mp;
  PrimeGenerate();
  //cout<<prime[21471]<<"\n";
  //ofstream out;
  //out.open("out.txt");

  while(cin>>n)
  {
     cin>>m;
     //if(m==0 && n==0)
     //break;
     cnt=0;
     if(n>=m)
     {
        cout<<m<<" divides "<<n<<"!\n";
        //out<<m<<" divides "<<n<<"!\n";
        continue;
     }
     mp.clear();
     lld tmp = m;
     int j=0;
     int f=0;
     while(tmp>=v[j]*v[j])
     {
         if(tmp%v[j]==0)
         {
            tmp/=v[j];
            if(v[j]>n)
            {
               f=1;
               break;
            }
            mp[v[j]]++;
            cnt++;
            j=-1;
         }
         j++;
         if(j==v.size())
         break;
     }
     if(f)
     {
       //cout<<"1)\n";
       cout<<m<<" does not divide "<<n<<"!\n";
       //out<<m<<" does not divide "<<n<<"!\n";
       continue;
     }
     if(tmp>1)
     {
       if(tmp>n)
       {
         //cout<<"2)\n";
         cout<<m<<" does not divide "<<n<<"!\n";
         //out<<m<<" does not divide "<<n<<"!\n";
         continue;
       }
       mp[tmp]++;
       cnt++;
     }
     //cout<<mp.size()<<"\n";
     for(map<int,int>::iterator ii=mp.begin();ii!=mp.end();++ii)
     {
         a = 1;//ii->first;
         int t=0;//=n/a;
         int add=0;
         //cout<<t<<" "<<a<<" "<<n<<"\n";
         while(1)
         {
             a*=ii->first;
             add=n/a;
             t+=add;
             if(add==0)
             break;

         }
         if(t<ii->second)
         {
            f=1;
            break;
         }

         //cout<<ii->first<<" "<<ii->second<<"\n";
     }
     if(f)
     {
       //cout<<"3)\n";
       cout<<m<<" does not divide "<<n<<"!\n";
       //out<<m<<" does not divide "<<n<<"!\n";
     }
     else
     {
       cout<<m<<" divides "<<n<<"!\n";
       //out<<m<<" divides "<<n<<"!\n";
     }
  }
  //out.close();
  return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

#include <iostream>

#include <math.h>

#include <vector>

#include <map>

#include <sstream>

#include <fstream>

#define SIZE 46500

#define lld long long

using namespace std;

// sqrt of 2^31 is ~46400

vector<int> v;

int prime[SIZE];

void PrimeGenerate()

{

double p = sqrt(SIZE)+4;

for(int i=3;i<p;i+=2)

{

if(prime[i]==0)

{

for(int j=i+i;j<SIZE;j+=i)

prime[j]=1;

}

v.clear();

v.push_back(2);

for(int j=3;j<SIZE;j++)

{

if(prime[j]==0 && j%2!=0)

v.push_back(j);

}

int main()

{

int m,cnt;

lld a,n;

map<int,int> mp;

PrimeGenerate();

//cout<<prime[21471]<<"\n";

//ofstream out;

//out.open("out.txt");

while(cin>>n)

{

cin>>m;

//if(m==0 && n==0)

//break;

cnt=0;

if(n>=m)

{

cout<<m<<" divides "<<n<<"!\n";

//out<<m<<" divides "<<n<<"!\n";

continue;

}

mp.clear();

lld tmp = m;

int j=0;

int f=0;

while(tmp>=v[j]*v[j])

{

if(tmp%v[j]==0)

{

tmp/=v[j];

if(v[j]>n)

{

f=1;

break;

}

mp[v[j]]++;

cnt++;

j=-1;

}

j++;

if(j==v.size())

break;

}

if(f)

{

//cout<<"1)\n";

cout<<m<<" does not divide "<<n<<"!\n";

//out<<m<<" does not divide "<<n<<"!\n";

continue;

}

if(tmp>1)

{

if(tmp>n)

{

//cout<<"2)\n";

cout<<m<<" does not divide "<<n<<"!\n";

//out<<m<<" does not divide "<<n<<"!\n";

continue;

}

mp[tmp]++;

cnt++;

}

//cout<<mp.size()<<"\n";

for(map<int,int>::iterator ii=mp.begin();ii!=mp.end();++ii)

{

a = 1;//ii->first;

int t=0;//=n/a;

int add=0;

//cout<<t<<" "<<a<<" "<<n<<"\n";

while(1)

{

a*=ii->first;

add=n/a;

t+=add;

if(add==0)

break;

}

if(t<ii->second)

{

f=1;

break;

}

//cout<<ii->first<<" "<<ii->second<<"\n";

}

if(f)

{

//cout<<"3)\n";

cout<<m<<" does not divide "<<n<<"!\n";

//out<<m<<" does not divide "<<n<<"!\n";

}

else

{

cout<<m<<" divides "<<n<<"!\n";

//out<<m<<" divides "<<n<<"!\n";

}

//out.close();

return 0;

}

Category: Number Theory

836

12241

12542

12517

10780

10394

11347

11415

10856

10139

Archives

Categories