P3307 72分求调

code:

#include<bits/stdc++.h>
using namespace std;
long long m;
long long cnt,prim[10000001],mu[10000001];
bool v[10000001];
long long qpow(long long a,long long b) {
	b%=1000000006;
	long long res=1;
	while(b) {
		if(b&1) res*=a,res%=1000000007;
		a=a*a,a%=1000000007;
		b>>=1;
	}
	return res;
}
void init() {
	mu[1]=1;
	for(int i=2;i<=10000000;i++) {
		if(!v[i]) prim[++cnt]=i,mu[i]=-1;
		for(int j=1;j<=cnt&&prim[j]*i<=10000000;j++) {
			v[prim[j]*i]=1;
			if(i%prim[j]==0) {
				mu[i*prim[j]]=0;
				break;
			}
			mu[i*prim[j]]=-mu[i];
		}
		mu[i]+=mu[i-1];
		mu[i]%=1000000007;
	} 
}
long long phi(long long n) {
	long long res=n;
	for(int i=2;i*i<=n;i++) {
		if(n%i==0) {
			res=res/i*(i-1);
			while(n%i==0) n/=i;
		} 
	}
	if(n>1) res=res/n*(n-1);
	return res;
}
void sol1(long long n) {
	m=2;
	long long l=1;
	while(l<=n) {
		long long r=n/(n/l);
		m+=(mu[r]-mu[l-1])%1000000007*(n/l)%1000000007*(n/l)%1000000007*(n/l+3)%1000000007;
		m%=1000000007;
		l=r+1;
	}
	m*=166666668;
	m%=1000000007;
} 
long long f(long long n) {
	return qpow(m-1,n)+(n%2==1?1-m:m-1);
}
long long pri[2000];
long long sum[2000];
long long ans=0;
void co(long long n) {
	for(int i=2;i*i<=n;i++) {
		if(n%i==0) {
			cnt++;
			pri[cnt]=i;
			sum[cnt]=0;
			while(n%i==0) sum[cnt]++,n/=i;
		} 
	}
	if(n) 
		cnt++,pri[cnt]=n,sum[cnt]=1;
}
void sol(long long i,long long d,long long phi,long long n) {
	if(i==cnt+1) {
		ans=(ans+(phi*f(n/d))%1000000007)%1000000007;
		return;
	}
	sol(i+1,d,phi,n);
	d=d*pri[i]%1000000007,phi=phi*(pri[i]-1)%1000000007;
	sol(i+1,d,phi,n);
	for(int j=2;j<=sum[i];j++)
		d*=pri[i]%1000000007,phi=phi*pri[i]%1000000007,sol(i+1,d,phi,n);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	init();
	long long t;
	cin>>t;
	cnt=0;
	while(t--) {
		long long n,a;
		cin>>n>>a;
		sol1(a);
		co(n);
		sol(1,1,1,n);
		cout<<((ans*qpow(n,1000000005))%1000000007+1000000007)%1000000007<<endl;
		ans=cnt=0;
	}
	return 0;
}