Code:
#include#include #define setIO(s) freopen(s".in","r",stdin)#define ll long long #define ull unsigned long long #define maxn 3000000#define mod 1000000007 #define inv 500000004 using namespace std;using namespace tr1;int vis[maxn],prime[maxn],tot; ll phi[maxn]; unordered_map ansphi;void init(){ phi[1] = 1; for(int i=2;i