## 11889 - Benefit

Moderator: Board moderators

patsp
New poster
Posts: 12
Joined: Tue Sep 21, 2010 8:51 pm

### 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.
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

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

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 .....
patsp
New poster
Posts: 12
Joined: Tue Sep 21, 2010 8:51 pm

### Re: 11889 - Benefit

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...
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
New poster
Posts: 1
Joined: Tue Oct 23, 2012 11:59 am

### Re: 11889 - Benefit

thanks to plamplam and his examples....
Masum
New poster
Posts: 9
Joined: Tue Jul 10, 2012 11:39 am

### Re: 11889 - Benefit

naseef_07cuet wrote: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
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;
}
Fancy
brianfry713
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);
Check input and AC output for thousands of problems on uDebug!
Sabiha_Fancy
New poster
Posts: 24
Joined: Mon Jul 16, 2012 3:43 pm

### Re: 11889 - Benefit

After removing that line i am still getting wrong answer.
Fancy
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11889 - Benefit

Input:

Code: Select all

``````1
14 97692``````
AC output:

Code: Select all

``13956``
Check input and AC output for thousands of problems on uDebug!
@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

### 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
brianfry713
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!
rosynirvana
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