11889  Benefit
Moderator: Board moderators
Re: 11889  Benefit
What exactly do you want explained? Problem statement?
For some tips on how to solve it, take a look at some posts above.
For some tips on how to solve it, take a look at some posts above.
Re: 11889  Benefit
I still haven't solved this problem. I mean I got AC after getting 8 Runtime errors, 7 Wrong Answers and 2 Time Limits . But I don't know yet how the same code can get AC and Runtime Error. My AC code randomly gets AC or Runtime Error and this is very confusing. But anyway if you are getting consecutive Wrong Answers, then here are some cases.
I generated the first 450 primes and got AC.
I generated the first 450 primes and got AC.
Code: Select all
10
5 772195
1 1
1 903389
8 9
8 16
60 150
60 240
357 111384
56 10696
8866 1844128 (Thanks to ?ab for providing me this test case, I got AC after trying with this one :))
Code: Select all
154439
1
903389
NO SOLUTION
16
NO SOLUTION
16
936
191
5408
You tried your best and you failed miserably. The lesson is 'never try'. Homer Simpson
 shaon_cse_cu08
 New poster
 Posts: 50
 Joined: Tue May 25, 2010 9:10 am
 Contact:
11889  Benefit : WA WA!!
Code: Select all
Code Removed After AC :wink:
Last edited by shaon_cse_cu08 on Thu May 30, 2013 1:12 pm, edited 1 time in total.
I'll keep holding on...Until the walls come tumbling down...And freedom is all around .....
Re: 11889  Benefit
I can't say why your approach does not work, but try this case:shaon_cse_cu08 wrote:Hello every1... My code gives Correct answer for every Input i have tested... But I can't understand Why WA... Plz help me...
input:
Code: Select all
1
36 4680

 New poster
 Posts: 1
 Joined: Tue Oct 23, 2012 11:59 am
Re: 11889  Benefit
thanks to plamplam and his examples....
Re: 11889  Benefit
You are given a, c, you have to find the minimum b such that Lcm(a,b)=c. So c must be divisible by a, otherwise there is no such b. Now, for a prime p dividing a or b, Lcm(a,b)= product of p^{max(e1, e2)} where e1=power of p in prime factorization of a, e2 = power of b. Use this.naseef_07cuet wrote:Can anyone explain me about the problem?

 New poster
 Posts: 24
 Joined: Mon Jul 16, 2012 3:43 pm
Re: 11889  Benefit
Help me. I am getting wrong answer for this problem.
here is my code
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#define N 1000000
using namespace std;
bool a[N];
vector<int> primelist;
void seive()
{
int i,j,k;
memset(a,true,sizeof(a));
a[0]=a[1]=false;
for(i=4; i<N; i+=2)
{
a=false;
}
for(i=3; i*i<=N; i+=2)
{
if(a)
{
j = i*i;
while(j<N)
{
a[j]=false;
j = j+(2*i);
}
}
}
primelist.clear();
primelist.push_back(2);
for(i=3; i<N; i+=2)
{
if(a)
{
primelist.push_back(i);
}
}
}
int main()
{
int T,A,C,B,i,prime,n;
seive();
scanf("%d",&T);
while(T)
{
scanf("%d%d",&A,&C);
if(C%A != 0)
{
printf("NO SOLUTION\n");
continue;
}
B=1;
n=C;
i=0;
printf("%d ",primelist);
while(primelist<=sqrt((double)C))
{
prime = 1;
while(1)
{
if(n%primelist == 0)
{
prime *= primelist;
n /= primelist;
}
else
break;
}
if(A%prime != 0)
B *= prime;
i++;
}
if(B==1)
B = C/A;
printf("%d\n",B);
}
return 0;
}
here is my code
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#define N 1000000
using namespace std;
bool a[N];
vector<int> primelist;
void seive()
{
int i,j,k;
memset(a,true,sizeof(a));
a[0]=a[1]=false;
for(i=4; i<N; i+=2)
{
a=false;
}
for(i=3; i*i<=N; i+=2)
{
if(a)
{
j = i*i;
while(j<N)
{
a[j]=false;
j = j+(2*i);
}
}
}
primelist.clear();
primelist.push_back(2);
for(i=3; i<N; i+=2)
{
if(a)
{
primelist.push_back(i);
}
}
}
int main()
{
int T,A,C,B,i,prime,n;
seive();
scanf("%d",&T);
while(T)
{
scanf("%d%d",&A,&C);
if(C%A != 0)
{
printf("NO SOLUTION\n");
continue;
}
B=1;
n=C;
i=0;
printf("%d ",primelist);
while(primelist<=sqrt((double)C))
{
prime = 1;
while(1)
{
if(n%primelist == 0)
{
prime *= primelist;
n /= primelist;
}
else
break;
}
if(A%prime != 0)
B *= prime;
i++;
}
if(B==1)
B = C/A;
printf("%d\n",B);
}
return 0;
}
Fancy

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 11889  Benefit
Remove line 60:
printf("%d ",primelist);
printf("%d ",primelist);
Check input and AC output for thousands of problems on uDebug!

 New poster
 Posts: 24
 Joined: Mon Jul 16, 2012 3:43 pm

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 11889  Benefit
Input:AC output:
Code: Select all
1
14 97692
Code: Select all
13956
Check input and AC output for thousands of problems on uDebug!
Re: 11889  Benefit
Getting WA...getting correct answer for all test cases given in this thread...
Code: Select all
Code Removed.
Last edited by @ce on Tue Jul 02, 2013 4:31 pm, edited 1 time in total.
@ce

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 11889  Benefit
If C is divisible by A, then B is the smallest multiple of (C / A) where LCM(A, B) = C and B is less than or equal to C.
Check input and AC output for thousands of problems on uDebug!

 New poster
 Posts: 4
 Joined: Thu Oct 03, 2013 10:16 pm
Re: 11889  Benefit
There is no need to factor a or c.
c % a != 0 > NO SOLUTION
factoring gcd(c/a, a) is enough
c % a != 0 > NO SOLUTION
factoring gcd(c/a, a) is enough