## 10139 - Factovisors

Moderator: Board moderators

Thank you so much

Well, to be serious, OK, I will think about your hint, as it is
really a sort of hint Although a quite quite small hint.

Sedefcho
A great helper

Posts: 375
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Larry, thank you for the small hint.
Although I knew it even before I started implementing some code
that we SHOULD NOT pre-generate 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.

Sedefcho
A great helper

Posts: 375
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### 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.
Wei
New poster

Posts: 23
Joined: Sat Jul 24, 2004 5:37 pm

Try this test case:

Code: Select all
`31 402653184`

The answer must be "does not divide," since:

31! = 2^26 3^14 ... 29^1 31^1
402653184 = 2^27 3^1
mf
Guru

Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland

Well~~Thx~~

I finally got AC~~
Wei
New poster

Posts: 23
Joined: Sat Jul 24, 2004 5:37 pm

### 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).

Code: Select all
` m = m/gcd (m,n)  `

then i did the same with n-1, 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 programming-challenges 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);}    `

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
CodeJerk
New poster

Posts: 4
Joined: Sun May 29, 2005 1:08 am
Location: India

### Re: 10139 Better Algorithm ?

CodeJerk wrote:
Code: Select all
`do{    ...  } while (true);`

I think it's the endless loop that gives you TLE.

dumb dan
Learning poster

Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

### 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.
CJ
CodeJerk
New poster

Posts: 4
Joined: Sun May 29, 2005 1:08 am
Location: India

Read until you hit EOF.Something along the line of...
Code: Select all
` while ( 2 == scanf("%d %d", &a, &b) ) { }`

Regards,
Suman.
sumankar
A great helper

Posts: 288
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta

### 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[i])
{
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[i]*prime[i]<=m;i++) //check if M is prime
if(m%prime[i]==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[i]);
if(k==0)continue;
x=0;
for(j=prime[i];j<=n;j+=prime[i])
{
y=j;
x+=howfac(&y,prime[i]);
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
naguib
New poster

Posts: 5
Joined: Sat Mar 12, 2005 3:29 am

### Accepted

I just rewrote the code and I got Accepted thx anyway
naguib
New poster

Posts: 5
Joined: Sat Mar 12, 2005 3:29 am

### 10139 - Factovisor why TLE

Never mind it. Found the bug.
Thanx anyway to those who tried to help me.
binusian0600618124
New poster

Posts: 2
Joined: Fri Jun 30, 2006 4:22 pm

Thanks a lot.There was a silly mistake in my code and the test case 94764610 284293833 helped me finding that.
Sumon
New poster

Posts: 17
Joined: Fri May 30, 2003 8:14 pm

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.
ashipm01
New poster

Posts: 2
Joined: Wed Oct 11, 2006 11:09 pm

i am in great problem!
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[len-1];   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 = *p-48 + carry+ (a*b);         *p = (*p-48 + 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<=len-1;i++)      mod=((p[i]-48)+mod*10)%num;   return (mod%num);}`

newton
Experienced poster

Posts: 162
Joined: Thu Jul 13, 2006 7:07 am