首页 > 其他 > 详细

密码解锁

时间:2019-06-25 23:55:58      阅读:92      评论:0      收藏:0      [点我收藏+]

标签:cnblogs   mce   scanf   sca   inline   inf   sin   def   include   

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

题解链接:https://www.cnblogs.com/cj-xxz/p/10812358.html

注意几个结论:

  1. μ(ij)=μ(i)μ(j)[gcd(i,j)==1]
  2. n以内无>1平方因子数个数=技术分享图片

考虑每个数j被哪些平方因子统计。因为j的约数的μ之和=[j==1],所以当j有大于1的平方因子时贡献=0,否则贡献=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;
}

 

密码解锁

标签:cnblogs   mce   scanf   sca   inline   inf   sin   def   include   

原文:https://www.cnblogs.com/pthws/p/11087302.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号