# 密码解锁

https://www.luogu.org/problemnew/show/P5348

1. μ(ij)=μ(i)μ(j)[gcd(i,j)==1]
2. n以内无＞1平方因子数个数=

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100005;
int t,p[N],mu[N],l,i,j;
bool v[N];
ll n,m,ans;
ll gcd(ll a,ll b)
{
if(!b)
return a;
return gcd(b,a%b);
}
inline int u(ll n)
{
int i,j,rtn=1;
for(i=2;i*i<=n;++i)
if(n%i==0)
{
j=0;
while(n%i==0)
n/=i,++j;
if(j>1)
return 0;
rtn=-rtn;
}
if(n>1)
rtn=-rtn;
return rtn;
}
ll S(int n,int m)
{//这里应该记忆化复杂度才对
ll rtn=0;
int d,i;
if(n==0)
return 0;
if(n==1)
return 1;
if(m==1)
{
for(i=1;i*i<=n;++i)
rtn+=mu[i]*(n/i/i);
return rtn;
}
for(d=1;d*d<m;++d)
if(m%d==0)
{
i=u(d);
rtn+=i*i*i*S(n/d,d);
i=u(m/d);
rtn+=i*i*i*S(n/(m/d),m/d);
}
if(d*d==m)
{
i=u(d);
rtn+=i*i*i*S(n/d,d);
}
return rtn;
}
int main()
{
scanf("%d",&t);
mu[1]=1;
for(i=2;i<=100000;++i)
{
if(!v[i])
{
p[++l]=i;
mu[i]=-1;
}
for(j=1;j<=l&&p[j]*i<=100000;++j)
{
v[p[j]*i]=true;
if(i%p[j]==0)
{
mu[p[j]*i]=0;
break;
}
else
mu[p[j]*i]=-mu[i];
}
}
while(t--)
{
scanf("%lld%lld",&n,&m);
ans=S(n/m,m)*u(m);
printf("%lld\n",ans);
}
return 0;
}

#include<cstdio>

#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100005;
int t,p[N],mu[N],l,i,j;
bool v[N];
ll n,m,ans;
ll gcd(ll a,ll b)
{
if(!b)
return a;
return gcd(b,a%b);
}
inline int u(ll n)
{
int i,j,rtn=1;
for(i=2;i*i<=n;++i)
if(n%i==0)
{
j=0;
while(n%i==0)
n/=i,++j;
if(j>1)
return 0;
rtn=-rtn;
}
if(n>1)
rtn=-rtn;
return rtn;
}
ll S(int n,int m)
{
ll rtn=0;
int d,i;
if(n==0)
return 0;
if(n==1)
return 1;
if(m==1)
{
for(i=1;i*i<=n;++i)
rtn+=mu[i]*(n/i/i);
return rtn;
}
for(d=1;d*d<m;++d)
if(m%d==0)
{
i=u(d);
rtn+=i*i*i*S(n/d,d);
i=u(m/d);
rtn+=i*i*i*S(n/(m/d),m/d);
}
if(d*d==m)
{
i=u(d);
rtn+=i*i*i*S(n/d,d);
}
return rtn;
}
int main()
{
scanf("%d",&t);
mu[1]=1;
for(i=2;i<=100000;++i)
{
if(!v[i])
{
p[++l]=i;
mu[i]=-1;
}
for(j=1;j<=l&&p[j]*i<=100000;++j)
{
v[p[j]*i]=true;
if(i%p[j]==0)
{
mu[p[j]*i]=0;
break;
}
else
mu[p[j]*i]=-mu[i];
}
}
while(t--)
{
scanf("%lld%lld",&n,&m);
ans=S(n/m,m)*u(m);
printf("%lld\n",ans);
}
return 0;
}



(0)
(0)