Thank you so much
![:)](./images/smilies/icon_smile.gif)
Well, to be serious, OK, I will think about your hint, as it is
really a sort of hint
![:)](./images/smilies/icon_smile.gif)
Moderator: Board moderators
Code: Select all
Cut after AC
Code: Select all
31 402653184
Code: Select all
m = m/gcd (m,n)
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);
}
I think it's the endless loop that gives you TLE.CodeJerk wrote:Code: Select all
do{ ... } while (true);
Code: Select all
while ( 2 == scanf("%d %d", &a, &b) ) {
}
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);
}