今天知识点是数论 考试真的是暴力啊 最后一题因为x₀ y₀爆零了让我很不爽啊  +60我就rank1了

D4T1  取球游戏

题目大意：

桌子上放着 N 个球，每个球都有一个编号，第i个球的编号为i。请你求出一共存在多少种不同的取法，使得取出的 M 个球编号的最小值恰 好为K。由于结果可能很大，请输出结果对10⁹+7（这是一个质数）取模的值。
数据范围：100%数据：n<=1000000,m<=1000000,1<=k<=n

思路：

这道题本意是让我们求Cⁿ_m^-_-^k₁ 那么我们就可以通过求逆元来求出组合数

顺利AC

#include<cstdio>
#include<algorithm>
using namespace std;
#define mod 1000000007ll
int n,m,k;
long long a[1000010];
long long ksm(long long x,long long y)
{
    long long sum=1;
    while(y)
    {
        if(y&1)sum=(sum*x)%mod;
        y=y>>1;
        x=x*x%mod;
    }
    return sum;
}
long long tmp=1;
long long ans=1;
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    n=n-k,m--;
    if(m==0)
    {
        printf("1");
        return 0;
    }
    for(int i=2;i<=n;i++) 
        tmp=(tmp*i)%mod;
    a[n]=ksm(tmp,mod-2);
    for(int i=n-1;i>=1;i--)
        a[i]=(a[i+1]*(i+1))%mod;
    ans=ans*tmp%mod*a[m]%mod*a[n-m]%mod;
    printf("%lld",ans);
    return 0;
}

D4T2 公约数问题

题目大意：

给定正整数 N，请你解决下面两个子任务。
1. 求有多少对(i, j)满足gcd(i,j)=1
2,求有多少对(i, j)满足gcd(i,j)为素数。
其中1<=i,j<=N

思路：

子任务1：其实所求就是2{ ∑φ(i)}-1 预处理欧拉函数值即可