题解：P6210 「SWTR-4」Easy Math Problems

· · 题解

题意：（题目已经说得简洁了）

思路

我们发现其实只需求： 对于某个 m，

\sum_{i = 1}^{n} \ [\gcd(d,n) \le c]

我们不妨令：

h(m)= [\gcd(d,n) \le c] f(m)= \sum_{i = 1}^{m} h(d)

显然 f(m) 单调不减，可以处理第一问。

当 d \ge n 时，\gcd(d,n)=\gcd(d \bmod n,n)，所以 h(m) 显然是周期性的，周期是 n，所以就只需要考虑 m<n 的情况就可以了。

f(m)= \sum_{k \mid n,k \le c} \sum_{k=1}^{\frac{m}{k}} [\gcd(i,\frac{n}{k})=1]

枚举 \gcd(i,n/k) 得：

f(m)= \sum_{d=1}^{n} \sum_{k \mid n,k \le c} \sum_{i=1}^{\frac{m}{k}} [d \mid i][d \mid \frac{n}{k}]*\mu(d)

令 d \ast k=T，显然有 \frac{m}{T} 个 i 满足 d \mid i。

所以

f(m)= \sum_{k \mid n,k \le c} \sum_{T \mid n} \mu(d)*\frac{m}{T}

即

f(m)= \sum_{T \mid n} \frac{m}{T}* \sum_{k \mid T,k \le c} \mu(\frac{T}{d})

令 g(T)=\sum_{d \mid T,d \le c}\mu(\frac{T}{d})。

那么现在考虑怎样求 g，枚举 n 的因数后爆算就行了。

感觉本题难点在高精度上

#include<bits/stdc++.h>
using namespace std;
int read(){ int x=0; bool flag=1; char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-') flag=0;ch=getchar();}
    while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return flag? x:-x;}
const int maxn=1e7+5;
const int SIZE_BIG=1e5+5;
int n,m,c;

int Mu[maxn],Yi[1005];
int F[maxn],g[1005];
int Prime[maxn],cnt;
bool vis[maxn];
void init()
{
    int i,j,num=0;
    Mu[1]=1;
    for(i=2;i<=n;i++)
    {
        if(vis[i]==0)
        {
            Prime[++cnt]=i;
            Mu[i]=-1; 
        }
        for(j=1;j<=cnt && i*Prime[j]<=n;j++)
        {
            vis[i*Prime[j]]=1;
            if(i%Prime[j]==0)
            {
                Mu[i*Prime[j]]=0;
                break;
            }
            Mu[i*Prime[j]]=-Mu[i];
        }
    }

    for(i=1;i*i<=n;i++)
    {
        if(n%i==0)
        {
            Yi[++num]=i;
            Yi[++num]=n/i;
        }
    }
    sort(Yi+1,Yi+1+num);
    num=unique(Yi+1,Yi+1+num)-Yi-1;
    for(i=1;i<=num;i++)
    {
        if(Yi[i]>c) break;
        for(j=i;j<=num;j++)
        {
            if(Yi[j]%Yi[i]==0)
            g[j]+=Mu[Yi[j]/Yi[i]];
        }
    }
    for(i=1;i<=num;i++)
    {
        for(j=Yi[i];j<=n;j+=Yi[i])
        F[j]+=g[i];
    }
    for(i=1;i<=n;i++) F[i]+=F[i-1];
}

char s[SIZE_BIG];
struct Big
{
    int a[SIZE_BIG],len;
    void Clear(){memset(a,0,sizeof(a));len=0;}
    void clear(){while(len>1 && a[len]==0) len--;}
    void read()
    {
        scanf("%s",s+1);
        len=strlen(s+1);
        for(int i=1;i<=len;i++)
        a[i]=(s[len-i+1]^48);
    }
    void write()
    {
        clear();
        for(int i=len;i>=1;i--)
        putchar(a[i]+48);
        putchar('\n');
    }
    int &operator [](int i){return a[i];}
    Big friend operator +(Big a,int b)
    {
        int i; a[1]+=b;
        for(i=1;i<=a.len;i++)
        {
            if(a[i]>=10)
            {
                a[i+1]+=a[i]/10;
                a[i]%=10;
                if(i==a.len)
                a.len++;
            }
        }
        a.clear();
        return a;
    }
    Big friend operator -(Big a,int b)
    {
        int i; a[1]-=b;
        for(i=1;i<=a.len;i++)
        {
            if(a[i]<0)
            {
                a[i]+=10;
                a[i+1]--;
            }
        }
        a.clear();
        return a;
    }
    Big friend operator -(Big a,Big b)
    {
        int i;
        for(i=b.len;i>=1;i--) a[i]-=b[i];
        for(i=1;i<=a.len;i++)
        {
            if(a[i]<0)
            {
                a[i]+=10;
                a[i+1]--;
            }
        }
        a.clear();
        return a;
    }
    Big friend operator *(Big a,int b)
    {
        int i;
        for(i=1;i<=a.len;i++) a[i]*=b;
        for(i=1;i<=a.len;i++)
        {
            if(a[i]>=10)
            {
                a[i+1]+=a[i]/10;
                a[i]%=10;
                if(i==a.len)
                a.len++;
            }
        }
        return a;
    }
    Big friend operator /(Big a,int b)
    {
        int i,x=0;
        for(i=a.len;i>=1;i--)
        {
            x=x*10+a[i];
            a[i]=x/b;
            x%=b;
        }
        a.clear();
        return a;
    }
    int friend operator %(Big a,int b)
    {
        int i,x=0;
        for(i=a.len;i>=1;i--)
        {
            x=x*10+a[i];
            a[i]=x/b;
            x%=b;
        }
        return x;
    }
}f,ans,L,R,Ans;
signed main()
{
    int i,kkk=0;
    n=read(),c=read(); init();
    f.read(); ans=f/F[n]*n; kkk=f%F[n];
    if(kkk==0)
    {
        ans=ans-n;
        for(i=n;i>=1;i--)
        {
            if(F[i]!=F[n])
            {
                ans=ans+(i+1);
                break;
            }
        }
    }
    else
    {
        for(i=0;i<n;i++)
        {
            if(kkk==F[i])
            {
                ans=ans+i;
                break;
            }
        }
    }
    ans.write(); ans.Clear();
    f.read(); f=f-1; kkk=f%n;
    ans=f/n*F[n]+F[kkk];
    f.Clear(); f.read(); kkk=f%n;
    Ans=f/n*F[n]+F[kkk];
    ans=Ans-ans; ans.write();
    return 0;
}