Page **4** of **6**

Posted: **Fri Mar 04, 2005 5:09 am**

by **Sedefcho**

Larry, that is really the most helpful answer I've ever received.

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.

Posted: **Sun Mar 06, 2005 2:01 am**

by **Sedefcho**

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.

### 10139 WA~~

Posted: **Sun Mar 20, 2005 5:29 pm**

by **Wei**

Posted: **Sun Mar 20, 2005 7:33 pm**

by **mf**

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

Posted: **Mon Mar 21, 2005 2:57 am**

by **Wei**

Well~~Thx~~

I finally got AC~~

### 10139 Better Algorithm ?

Posted: **Mon May 30, 2005 8:32 am**

by **CodeJerk**

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 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

### Re: 10139 Better Algorithm ?

Posted: **Mon May 30, 2005 10:42 am**

by **dumb dan**

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

### But is there an end condition?

Posted: **Mon May 30, 2005 2:56 pm**

by **CodeJerk**

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

Posted: **Mon May 30, 2005 3:36 pm**

by **sumankar**

Read until you hit EOF.Something along the line of...

Code: Select all

```
while ( 2 == scanf("%d %d", &a, &b) ) {
}
```

Regards,

Suman.

### 10139 Factovisors WA plz help

Posted: **Wed Oct 05, 2005 12:47 pm**

by **naguib**

#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**

### Accepted

Posted: **Wed Oct 05, 2005 8:10 pm**

by **naguib**

**I just rewrote the code and I got Accepted thx anyway**

### 10139 - Factovisor why TLE

Posted: **Sat Jul 01, 2006 7:11 am**

by **binusian0600618124**

Never mind it. Found the bug.

Thanx anyway to those who tried to help me.

Posted: **Tue Oct 10, 2006 9:23 am**

by **Sumon**

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

Posted: **Wed Oct 11, 2006 11:15 pm**

by **ashipm01**

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.

Posted: **Wed Mar 28, 2007 8:50 am**

by **newton**

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);
}
```