10139  Factovisors
Moderator: Board moderators
Larry, thank you for the small hint.
Although I knew it even before I started implementing some code
that we SHOULD NOT pregenerate all the primes up to 2^32  1.
It was pretty obvious.
Now I've designed a decent algorithm for solving this problem.
Although not the best one, of course.
So thank you, anyway.
Although I knew it even before I started implementing some code
that we SHOULD NOT pregenerate all the primes up to 2^32  1.
It was pretty obvious.
Now I've designed a decent algorithm for solving this problem.
Although not the best one, of course.
So thank you, anyway.
10139 WA~~
Code: Select all
Cut after AC
Last edited by Wei on Mon Mar 21, 2005 2:56 am, edited 1 time in total.
Try this test case:
The answer must be "does not divide," since:
31! = 2^26 3^14 ... 29^1 31^1
402653184 = 2^27 3^1
Code: Select all
31 402653184
31! = 2^26 3^14 ... 29^1 31^1
402653184 = 2^27 3^1
10139 Better Algorithm ?
Hi
I tried solving Problem: 10139 but got a Time Limit Exceeded error.
What I was doing was, starting from n, i was calculating the gcd(n,m) and dividing m by gcd(n,m).
then i did the same with n1, and so on, till m was reduced to 1, or n became 1.
Sometimes, one gets a large prime number as one of the factors, and to handle that i counted the no. of times that the gcd was consecutively 1. In case, this exceeded 50 times, I checked if m was prime, and if it was, exited with a negative answer.
This works fine on almost all inputs, and comes out pretty fast when i try it on my system, but always gives TLE on the programmingchallenges website.
the code is here
Can u plz suggest a better algo to solve this problem. I have tried looking my Number Theory books, but am still in the dark regarding this problem. I would be really grateful if u could help me out.
Thanks,
CJ
I tried solving Problem: 10139 but got a Time Limit Exceeded error.
What I was doing was, starting from n, i was calculating the gcd(n,m) and dividing m by gcd(n,m).
Code: Select all
m = m/gcd (m,n)
Sometimes, one gets a large prime number as one of the factors, and to handle that i counted the no. of times that the gcd was consecutively 1. In case, this exceeded 50 times, I checked if m was prime, and if it was, exited with a negative answer.
This works fine on almost all inputs, and comes out pretty fast when i try it on my system, but always gives TLE on the programmingchallenges website.
the code is here
Code: Select all
#include <iostream.h>
#include <math.h>
long gcd (long p,long q)
{
if (q == 0) return p;
else return (gcd (q, p%q));
}
bool isprime (long n)
{
for (int i = 3; i<=sqrt(n)+1 ; i+=2)
{
if (n%i == 0) {return (false);}
}
return (true);
}
int main()
{
do{
long n,m,saven, savem;
cin >>n>> m;
saven = n; savem = m;
bool flag = false;
int counter= 0; //prime check
if (n == 0 && m == 1) {flag = true;goto End;}
if (n==0 && m>1) {flag = false;goto End;}
if (m == 0) {flag = false;goto End;}
// to c if m divides n!62454TK
while ( n >= 1 && m >= 1)
{
if (m <= n) { flag = true; goto End;}
long g = gcd (m,n);
if (g==1) { counter++; if (counter == 50)
{ if (isprime (m)) {flag = false;break;}}
}
else counter = 0;
m = m/g; n = (n  1)*(n/g);
//cout << "n =" << n << " m = " << m << endl; //int x ; cin >> x;
if (m == 1) { flag = true; break; }
}
End:
if (flag == true) cout << savem <<" divides " << saven<<"!";
else cout << savem <<" does not divide " << saven<<"!";
cout << endl;
} while (true);
return (0);
}
Thanks,
CJ
Re: 10139 Better Algorithm ?
I think it's the endless loop that gives you TLE.CodeJerk wrote:Code: Select all
do{ ... } while (true);
But is there an end condition?
The question doesnt specify any end condition, like, for e.g., that the last input is 0 0, which is *not* to be processed.
If u got AC could you plz tell me what was the end condition u specified.
Thanks in advance.
CJ
If u got AC could you plz tell me what was the end condition u specified.
Thanks in advance.
CJ
Read until you hit EOF.Something along the line of...
Regards,
Suman.
Code: Select all
while ( 2 == scanf("%d %d", &a, &b) ) {
}
Suman.
10139 Factovisors WA plz help
#include<cstdio>
#include<string>
#include<cmath>
using namespace std;
//FILE *in=fopen("fact.in","r");
bool iscom[46502];
int prime[5000];
#ifdef __GNUC__
#define longlong long long
#else
#define longlong __int64
#endif
int howfac(longlong* n,int f)
{
//return how many factor F is in n
longlong ret=0;
while(((*n)%f)==0)
{
(*n)/=f;
ret++;
}
return ret;
}
int main()
{
longlong i,j,k,n,m,c=0,f,x,y,m2,div;
memset(iscom,0,sizeof(iscom));
for(i=2;i<=46350;i++)
{
if(!iscom)
{
prime[c]=i;
c++;
for(j=(i+i);j<=46500;j+=i)
iscom[j]=1;
}
}
//while(EOF!=fscanf(in,"%lld %lld",&n,&m))
while(EOF!=scanf("%lld %lld",&n,&m))
{
m2=m;
if(n>=m)
div=1;
else if(m==0)
div=0;
else if(n==0)
div=1;
else
{
f=1;
for(i=0;i<c && prime*prime<=m;i++) //check if M is prime
if(m%prime==0){f=0;break;}
if(f)
div=0;
else
for(i=0;i<c;i++) //check if all prime factors in M is in N! with enough quantity
{
k=howfac(&m,prime);
if(k==0)continue;
x=0;
for(j=prime;j<=n;j+=prime)
{
y=j;
x+=howfac(&y,prime);
if(x>=k)
break;
}
if(x<k)
{div=0;break;}
if(m==1)
{div=1; break;}
}
}
if(!div)
printf("%lld does not divide %lld!\n",m2,n);
else
printf("%lld divides %lld!\n",m2,n);
}
return 0;
}
If any body can find a mistake or a bug plz tell me I hope that the comments will clarify my algorithm
#include<string>
#include<cmath>
using namespace std;
//FILE *in=fopen("fact.in","r");
bool iscom[46502];
int prime[5000];
#ifdef __GNUC__
#define longlong long long
#else
#define longlong __int64
#endif
int howfac(longlong* n,int f)
{
//return how many factor F is in n
longlong ret=0;
while(((*n)%f)==0)
{
(*n)/=f;
ret++;
}
return ret;
}
int main()
{
longlong i,j,k,n,m,c=0,f,x,y,m2,div;
memset(iscom,0,sizeof(iscom));
for(i=2;i<=46350;i++)
{
if(!iscom)
{
prime[c]=i;
c++;
for(j=(i+i);j<=46500;j+=i)
iscom[j]=1;
}
}
//while(EOF!=fscanf(in,"%lld %lld",&n,&m))
while(EOF!=scanf("%lld %lld",&n,&m))
{
m2=m;
if(n>=m)
div=1;
else if(m==0)
div=0;
else if(n==0)
div=1;
else
{
f=1;
for(i=0;i<c && prime*prime<=m;i++) //check if M is prime
if(m%prime==0){f=0;break;}
if(f)
div=0;
else
for(i=0;i<c;i++) //check if all prime factors in M is in N! with enough quantity
{
k=howfac(&m,prime);
if(k==0)continue;
x=0;
for(j=prime;j<=n;j+=prime)
{
y=j;
x+=howfac(&y,prime);
if(x>=k)
break;
}
if(x<k)
{div=0;break;}
if(m==1)
{div=1; break;}
}
}
if(!div)
printf("%lld does not divide %lld!\n",m2,n);
else
printf("%lld divides %lld!\n",m2,n);
}
return 0;
}
If any body can find a mistake or a bug plz tell me I hope that the comments will clarify my algorithm

 New poster
 Posts: 2
 Joined: Fri Jun 30, 2006 4:22 pm
10139  Factovisor why TLE
Never mind it. Found the bug.
Thanx anyway to those who tried to help me.
Thanx anyway to those who tried to help me.
You can get the prime factors of the m and n (from two to n since it is n!) numbers and keep dividing out the prime factors from m until no more prime factors remain in m (return true) or until you reach n (return false).
I would not do it with BigInteger though because it seems the judge does not accept the BigInteger class. I got a compile error before on the Square root problem when I tried to use BigInteger, so I had to write my own BigInteger class.
I would not do it with BigInteger though because it seems the judge does not accept the BigInteger class. I got a compile error before on the Square root problem when I tried to use BigInteger, so I had to write my own BigInteger class.

 Experienced poster
 Posts: 162
 Joined: Thu Jul 13, 2006 7:07 am
 Location: Campus Area. Dhaka.Bangladesh
 Contact:
i am in great problem!
please say me why RE [signal 11]?
please say me why RE [signal 11]?
Code: Select all
#include <stdio.h>
#include <string.h>
void str_mul(char str1[],int n );
long is_divisible(char str[],long);
char *x;
main()
{
char str[2600];
char res[1001][2600];
long num,fact,temp;
x = str;
strcpy(res[0],"1");
fact = 1;
strcpy(str,"1");
while(fact!=1001)
{
x = str;
str_mul(str,fact);
strcpy(res[fact],str);
fact = fact + 1;
}
while(scanf("%ld %ld",&fact,&num)==2)
{
temp = fact;
if(!is_divisible(res[fact],num))
printf("%ld divides %ld!\n",num,temp);
else
printf("%ld does not devide %ld!\n",num,temp);
}
return 0;
}
void str_rev(char *str)
{
long len,i;
char *p,*q,temp;
len = strlen(str);
p = str;
q = &str[len1];
for(i=0;i<len/2;i++)
{
temp = *p;
*p = *q;
*q = temp;
p++;
q;
}
}
void str_mul(char str1[], int n)
{
char *p;
char res[10000],tem[10000];
int len1,carry,i,j,temp;
len1 = strlen(str1);
str_rev(str1);
carry=0;
memset(res,'0',sizeof(res));
p = res;
for(i=0;i<len1;i++)
{
carry = 0;
p = &res[i];
int t = n;
while(t)
{
int a = str1[i]48;
int b = t%10;
temp = *p48 + carry+ (a*b);
*p = (*p48 + carry + (a*b))%10 + 48;
carry=(temp/10);
p++;
t/=10;
}
if(carry)
*p = carry + 48;
}
if(carry)
p++;
*p = '\0';
for(i=strlen(res)1;i>=0;i)
{
*x = res[i];
x++;
}
*x = '\0';
}
long is_divisible(char p[], long num)
{
long mod=0;
long len,i;
len = strlen(p);
for(i=0;i<=len1;i++)
mod=((p[i]48)+mod*10)%num;
return (mod%num);
}