#include #include #include #include #include #include using namespace std; typedef long long LL; typedef long double LD; #define MAX(x,y) x>=y?x:y long long ans=0; typedef unsigned long long ULL; typedef long long LL; const ULL SQRT_MAX = 1ULL << 32; ULL multiply_mod(ULL x, ULL y, ULL mod) { if (x < SQRT_MAX && y < SQRT_MAX) return (x*y)%mod; ULL res = 0; ULL tmp = y%mod; while (x) { if ((x & 1) && (res += tmp) >= mod) res -= mod; tmp <<= 1; if (tmp >= mod) tmp -= mod; x >>= 1; } return res; } // calculates base^exp MOD mod (without overflow :-) ULL power_mod(ULL base, ULL exp, ULL mod) { ULL result = 1; while(exp) { if (exp&1) result = multiply_mod(result, base, mod); exp >>= 1; base = multiply_mod(base, base, mod); } return result; } int test(ULL n, ULL a) { ULL s = n-1; int r = 0; while (!(s & 1)) s >>= 1, r++; ULL t = power_mod(a, s, n); if (t == 1 || t == n-1) return 1; while (--r) if ((t = multiply_mod(t, t, n)) == n-1) return 1; return 0; } int isprime(ULL n) { if(n==3ULL||n==5ULL||n==7ULL||n==11ULL) return 1; if (n<2 || !(n & 1)) return n == 2; return test(n, 2) && test(n, 3) && test(n, 5) && test(n, 7) && test(n, 11); } #define MAXN 1000001 LL distinctFactorCount[MAXN]= {0LL}; LL primeList[200]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009}; LL primehash[1010]={0}; LL primeFactorization(LL N) { LL answer=1; LL temp=0; LL tempN=N; for(LL i=0LL; primeList[i]*primeList[i]<=N; i++) { temp=0; while(N%primeList[i]==0) { temp++; N/=primeList[i]; } answer=answer*(temp+1); } if(N>1) { answer=answer*2; } // printf("%lld",distinctFactorCount[12]) return answer; } LL isTwoDistinctFactor(LL N) { for(LL i=0LL; primeList[i]*primeList[i]