where are you getting the links to editorials from ???
There are no links on May Challenge page and neither there are links on the Wiki page .
The Wiki page is so outdated that it does not have links to Editorials after January contest .
@admin : please update wiki page .
@admin : Please tell me how others get to know about editorials page and their links earlier than even when these links are posted on contest page .
@betlista : Can you please tell where you got link to this editorial .
2 Likes
@gamabunta : when we are multiplying two large numbers which can be upto 10^18 cant we instead
multiplying by breaking them into parts … use (ab)%MOD=(a%MODb%MOD)%MOD. here also the ans will remain within 64 bit in the intermediate results.
I too used http://oeis.org/A014233 (mentioned in the editorial) during my approach. But that page says, “the primality of numbers < 264 can be determined by asserting strong pseudo-primality to all prime bases ≤ 37 (12th prime)”.
1018 is almost 260. Is it because of this small a difference, that testing with 9 primes will suffice? Or, am I missing something??
Here is my AC solution in Python (which tests with 12 primes of course).
I submitted my code in python of WITMATH during the contest and got AC. When i was submitting the same using C++ it was giving TLE though i had taken all steps to prevent overflow. Please can anyone help. Here’s my part of the code where repeated squarring is done:
#include
#include
using namespace std;
unsigned long long int mult (
unsigned long long int a,
unsigned long long int b,
unsigned long long int c
)
{
unsigned long long int x=0,y=a%c;
while(b>0)
{
if(b%2==1)
{
x=(x+y);
if(x>c) x=x%c;
}
y=(y*2);
if(y>c) y=y%c;
b/=2;
}
return x%c;
}
unsigned long long int modulo (
unsigned long long int a,
unsigned long long int b,
unsigned long long int c
)
{
unsigned long long int x = 1;
unsigned long long int y = a;
while (b>0)
{
if (b%2==1) x = mult(x,y,c);
y = mult(y,y,c);
b = b/2;
}
return x%c;
}
I was able to figure out that v should find out the largest prime number <= the given number. How ever I dint know to get rid of tle. Also I was not able to prove that fi(i)/i is max for only prime numbers. 4/5 < 97/99.
Let N = p1r1p2r2…pkrk
φ(N)/N = ((p1 - 1) / p1)((p2 - 1) / p2)…((pk - 1) / pk)
For some N, let P be the largest prime less than or equal to N, and C be some composite number less than or equal to N.
But by definition of P (largest prime less than N), C must be a product of primes less than or equal to P.
C = q1s1q2s2…qtst
Where each qi ≤ P
φ©/C = ((q1 - 1) / q1)((q2 - 1) / q2)…((qk - 1) / qk)
We know that
((a - 1) / a) ≤ ((b - 1) / b) if a ≤ b
Thus
φ©/C ≤ ((P - 1) / P)t … (because there were t terms)
where t ≥ 2
Lastly, we know that since ((P - 1) / P) < 1
((P - 1) / P) > ((P - 1) / P)t … for any t ≥ 2
Thus
φ©/C < ((P - 1) / P)
or
φ©/C < φ§/P
Hence the answer will always be the largest prime less than (or equal to) N.
1 Like
Admin can u plz chk CodeChef: Practical coding for everyone Even after using miller rabin and optimised modular exponation and product, I m getting TLE…
Before my code used to take 3-4 sec in my cases. Now only 31 ms. Still TLE 
Please chk…
links available under recent questions on home page
In my settings I have notifications enabled:
2 Likes
sorry it should be (a%MOD*b%MOD)%MOD
In the question the MOD is the number n which we are checking for primality . Thus , n<= 10^18 so the terms a%MOD and b%MOD will at max be 10^18 - 1 and (a%mod * b%mod) will still overflow
In the sequence, the 9th term is more than 3 x 1018.
The 8th term is much less than 1 x 1018.
So the smallest composite number that Miller Rabin will call prime with the first 8 bases is smaller than the numbers we are considering and we may run in to numbers that fail the test.
Using 9 primes assures that the smallest number that will fail the test is larger than the largest number we are considering.
1 Like
Setter and Tester’s solution links are not working
2 Likes
same here hehe… one of the shortest solutions I have ever written. Just one while loop with only one statement
1 Like
Oops! I didn’t check out the numbers in the sequence. Somehow, just managed to read the comment there!!
I was able to figure out that v should find out the largest prime number <= the given number. How ever I dint know to get rid of tle. Also I was not able to prove that fi(i)/i is max for only prime numbers. 4/5 < 97/99. Can some bosy plz tell how to prove it?
tester’s solution…classic
2 Likes