This problem can be transformed into a problem of evaluating sums of the form

over a system of linear congruences where are distinct prime factors of the Carmichael totient , and subsequently adding up the sums using the inclusion-exclusion principle based on the number of equations chosen in each system. The value of depends on . This algorithm can be derived from the constraint and the observation that when the number of unconcealed messages for is minimum. Ergo, this algorithm is equivalent to summing up all potential candidates for and then subtracting those candidates that fail to meet the constraints. The prime factorization for large numbers in the ballpark of can be computed rapidly using the Pollard's rho algorithm. Some care is needed to prevent loss of precision while dividing big numbers in Pollard's algorithm. Each system of linear congruences can be solved via the Chinese remainder theorem.

include

include

include

include

include

using namespace std;

long gcd(long x, long y) { long r; while(y!=0) { r=x%y; x=y; y=r; } return x; }

int main() { long phi,p,q, e, min=9999999,noum,ans=0; cin>>p>>q;
phi=(p-1)(q-1); for(e=2;e(gcd(e-1,q-1)+1); if(noum