例题

例1.沙拉公主的困惑

题目入口

题解

我们知道 \(gcd(m!+k,m!)=gcd(k,m!)\)

若\(k>m!\) 不妨令\(k=m!+c\)

于是\(gcd(k,m!)=gcd(c,m!)\)

我们目标求\(1-n!\)中\(gcd(i,m!)==1\)的个数

可以将\(n!\)分成\(n!/m!\)份

每一份为\(m!\) 其中与\(m!\)互质的数的个数为\(\phi(m!)\)

当m为质数时\(\phi(m!)=\phi((m-1)!)*(m-1)\)

当m不为质数时 \(\phi(m!)=\phi((m-1)!)*m\)

所以答案为 \(\frac{n!}{m!\phi(m!)}\)

注意本题又模数与除数非互质的情况，也就是\(r|m!\),此时重新处理阶乘即可

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+5;
int prime[N],phi[N],cnt;
bool vis[N];
int fac[N];
int x,y;
int exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    int res=exgcd(b,a%b,x,y);
    int tmp=x;
    x=y;
    y=tmp-(a/b)*y;
    return res;
}
void init(int n,int mod)
{
    phi[1]=1;
    fac[0]=fac[1]=1;
    for(int i=2;i<=n;i++)
    {
        fac[i]=fac[i-1]*i%mod;
        if(!vis[i]) prime[++cnt]=i,phi[i]=phi[i-1]*(i-1)%mod;
        else phi[i]=phi[i-1]*i%mod;
        for(int j=1;prime[j]*i<=n;j++)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}
int qpow(int a,int n,int mod)
{
    int res=1;
    while(n)
    {
        if(n&1) res=res*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return res;
}

signed main()
{
    int t,mod;
    cin>>t>>mod;
    init(N-4,mod);
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        if(m%mod) cout<<fac[n]*phi[m]%mod*qpow(fac[m],mod-2,mod)%mod<<endl;
        else
        {
            int tmp=1;
            for(int i=m+1;i<=n;i++) (tmp*=i)%=mod;
            cout<<tmp*phi[m]%mod<<endl;
        }
    }
    return 0;
}

例2.Domino(easy version)

题目入口

在这里插入图片描述

题解

设\(a=p_1 ^ {a_1} * p_2 ^ {a_2} * p_3 ^ {a_3}...p_n ^ {a_n}\) (\(p_1,p_2...\)为\(a\)的质因数，\(b=k_1 ^ {b_1} * k_2 ^ {b_2} * k_3 ^ {b_3}...k_n ^ {b_n} \((\)k_1,k_2...\)为\(b\)的质因数），则\(a\)可以在\(cnt1=a_1+a_2+a_3...a_n\)的次数内变成\(1\)，b能够在 \(cnt2=b_1+b_2+b_3...+b_n\)的次数内变成\(1\)，于是可以发现，若\(k>cnt1+cnt2\)，两个数在\(cnt1+cnt2\)操作后无法操作，输出NO，在\(k<cnt1+cnt2\)时，特判\(k=1\)的情况即可。本题分解质因数可用欧拉筛预处理。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+5;
int prime[N];
bool vis[N];
void euler()
{
    vis[1]=true;
    int cnt=0;
    for(int i=2;i<=N-5;i++)
    {
        if(!vis[i]) prime[++cnt]=i;
        for(int j=1;i*prime[j]<=N-5;j++)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}
signed main()
{
    int t;
    cin>>t;
    euler();
    while(t--)
    {
        int a,b,k;
        scanf("%lld %lld %lld",&a,&b,&k);
        int tmpa=a,tmpb=b;
        int cnt1=0,cnt2=0;
        if(a>N-5||vis[a])
        for(register int j=1; prime[j]*prime[j]<=a; j++)
        {
            if(a%prime[j]==0)
            {
                while(a%prime[j]==0)
                {
                    a/=prime[j];
                    cnt1++;
                }
            }
        }
        if(a>1) cnt1++;
        if(b>N-5||vis[b])
        for(register int j=1; prime[j]*prime[j]<=b; j++)
        {
            if(b%prime[j]==0)
            {
                while(b%prime[j]==0)
                {
                    b/=prime[j];
                    cnt2++;
                }
            }
        }
        if(b>1) cnt2++;
        if(cnt1+cnt2<k) printf("No\n");
        else if(k==1)
        {
            if((tmpa%tmpb==0||tmpb%tmpa==0)&&tmpa!=tmpb) printf("Yes\n");
            else if(tmpa==tmpb) printf("No\n");
            else printf("No\n");
        }
        else printf("Yes\n");
    }
    return 0;
}

例3.Strange Function

题目入口在这里插入图片描述

题解

\(f[x]\)表示不被\(x\)整除的最小的数，设其为\(a\)，则对\(x\)必存在因子\(1,2....a-1\),也就是说\(x\)存在约数\(a_1=lcm(1,2,3,...a-1)\)，由于\(a\)不被整除，所以\(x\)不存在约数\(a_2=lcm(1,2,...a)\)，在\(1-n\)中\(a_1\)的倍数有\(n/a_1\)个，\(a_2\)的倍数有\(n/a_2\)个，由于\(a_1|a_2\)，所以是\(a_1\)倍数但不是\(a_2\)倍数的有\(n/a_1-n/a_2\)个，且这些数的大小为\(a\)，循环到\(lcm\)大于\(n\)的时候停止即可

代码

#include<bits/stdc++.h>
#define int long long
const int mod=1e9+7;
using namespace std;
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int lcm(int a,int b)
{
    return a/gcd(a,b)*b;
}
void solve()
{
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        int lcmm=1;
        int tmp=2;
        int res=0;
        while(lcmm<=n)
        {
            int k1=n/lcmm;
            lcmm=lcm(lcmm,tmp);
            tmp++;
            int k2=n/lcmm;
            res+=(k1-k2)*(tmp-1);
            res%=mod;
        }
        cout<<res<<endl;
    }
}
signed main()
{
    solve();
    return 0;
}

借鉴博客https://blog.csdn.net/jziwjxjd/article/details/118558335?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522163184074316780271543979%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=163184074316780271543979&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-3-118558335.pc_search_ecpm_flag&utm_term=C.+Strange+Function&spm=1018.2226.3001.4187

例4.约数和

题目入口

题目描述

对于一个数 XX，函数 f(X)f(X) 表示 XX 所有约数的和。例如：f(6)=1+2+3+6=12f(6)=1+2+3+6=12。对于一个 XX，Smart 可以很快的算出 f(X)f(X)。现在的问题是，给定两个正整数 X,Y(X<Y)X,Y(X<Y)，Smart 希望尽快地算出 f(X)+f(X+1)+……+f(Y)f(X)+f(X+1)+……+f(Y)的值，你能帮助 Smart 算出这个值吗？

输入格式

输入文件仅一行，两个正整数 XX 和 Y(X<Y)Y(X<Y)，表示需要计算 f(X)+f(X+1)+\dots +f(Y)f(X)+f(X+1)+⋯+f(Y)。

输出格式

输出只有一行，为 f(X)+f(X+1)+\dots+f(Y)f(X)+f(X+1)+⋯+f(Y) 的值。

输入#1

2 4

输出#1

输入#2

123 321

输出#2

题解

我们知道，在\(1-n\)中，若\(a<n\)，则\(a\)的倍数有\(n/a\)个，因此一种暴力的做法便是枚举约数\(1-y\)在\(x-y\)的倍数，复杂度\(O(y)\)，超时，于是我们得想新方法。我们注意到我们需要知道的只是以\(1-y\)为约数的数有多少个，而大部分数的个数相同，如\(1-100\)内以\(51，52，53……100\)为约数的个数都只有一个，于是我们想到整除分块。易得答案为\(∑_1^y( y / i - x-1 / i ) * i\)。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int x,y;
signed main()
{
    cin>>x>>y;
    int res=0;
    for(int l=1,r;l<=y;l=r+1)
    {
        if(y/l)
            r=y/(y/l);
        else break;
        res+=(y/l)*(r-l+1)*(l+r)/2;
    }
    for(int l=1,r;l<=y;l=r+1)
    {
        if((x-1)/l)
             r=(x-1)/((x-1)/l);
        else break;
        res-=(x-1)/l*(r-l+1)*(l+r)/2;
    }
    cout<<res<<endl;
    return 0;
}