11889 - Benefit

[patsp]

What exactly do you want explained? Problem statement?
For some tips on how to solve it, take a look at some posts above.

[plamplam]

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.

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

[shaon_cse_cu08]

Code: Select all

Code Removed After AC  :wink: 

[patsp]

Hello every1... My code gives Correct answer for every Input i have tested... But I can't understand Why WA... Plz help me...

I can't say why your approach does not work, but try this case:

input:

Code: Select all

1
36 4680

My solution outputs 520, while yours outputs 4680.

[SDU_Phonism]

thanks to plamplam and his examples....

[Masum]

Can anyone explain me about the problem?

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.

[Sabiha_Fancy]

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

[brianfry713]

Remove line 60:
printf("%d ",primelist);

[Sabiha_Fancy]

After removing that line i am still getting wrong answer.

[brianfry713]

Input:

Code: Select all

1
14 97692

AC output:

Code: Select all

13956

[@ce]

Getting WA...getting correct answer for all test cases given in this thread...

Code: Select all

Code Removed.

[brianfry713]

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.

[rosynirvana]

There is no need to factor a or c.
c % a != 0 -> NO SOLUTION

factoring gcd(c/a, a) is enough