SPOJ ETFS

Revision en2, by Komyona_neko, 2016-12-03 11:59:28

Problem
My solution : solution
I was trying to solve this problem. It asks me to print phi(n) for n=a to b(inclusive). where,

0<a<b<10^14
and b-a<10^5
My solution is,
first do sieve and save all primes <= 10^7 in a vector prm. Then, run a segmented sieve to mark which ones are prime/composite in the range [a,b]. Then do another segmented sieve to calculate phi(n) in range [a,b].
I used long long(also tried unsigned long long) almost everywhere, but i'm getting WA. Can someone give me some corner cases/reason why I may be getting WA.
Thank you.

Tags #wronganswer, where wrong, bug in code, euler-totient, segmented sieve

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Komyona_neko 2016-12-03 11:59:28 38
en1 English Komyona_neko 2016-12-03 11:58:25 638 Initial revision (published)