MODIFYING PROBLEM B OF GOODBYE 2023

Revision en3, by SadArtira, 2023-12-31 06:45:30

I used an prime factorization of the final number x as follows

Assume x exists and = p1^q1 * p2^q2... and so on where p1<p2<p3<....

For the largest divisor I divide x by p1 so b=x/p1;

Now for second largest (i.e. a) I have two choices I have to compare between p1^2(if q1=1 then we don't have this choice) and p2 If p1^2>p2 then the second largest should be a=x/p2; else a=x/(p1^2);

consider the first one x/p2=a; and x/p1=b; or, a*p2=b*p1; Eq-1

let m be the gcd of (a,b) then dividing both sides of Eq-1 by m(let a/m=a1 and b/m=b1) a1*p2=b1*p1; now a1 doesn't have any common factors with b1 so it completely divides p1 similarly, p1 doesn't have any common factor with p2 so it completely divides a1

Hence a1=p1 and b1=p2;

So if a1 and b1 are not primes this fails as we don't get them as the largest and second largest numbers.

now considering the second case.(Only applicable if q1>1) a=(x/p1^2) and b=(x/p1)
or, p1^2*a=b*p1 or, p1=(b/a);

Hence it is clear that if a divides b and b/a is prime then only it holds otherwise it fails

I am not quite sure whether there are some more conditions or Am i missing something?

I submitted my code, It ran cause the test cases were only those which gave a and b 239748609

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English SadArtira 2023-12-31 06:46:14 0 Tiny change: 'ose which gave a and b \n[submis' -> 'ose which have a and b as answers \n[submis' (published)
en4 English SadArtira 2023-12-31 06:46:00 14 Tiny change: 'ose which gave a and b \n[submis' -> 'ose which have a and b as answers \n[submis'
en3 English SadArtira 2023-12-31 06:45:30 48
en2 English SadArtira 2023-12-31 06:44:59 108
en1 English SadArtira 2023-12-31 06:42:24 1222 Initial revision (saved to drafts)