费马小定理
图 1：费马小定理

费马小定理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int MOD=1e9+7;
int quick(int x,int y){
    int result=1;
    while(y!=0){
    if(y&1)result=((result%MOD)*x)%MOD;
    x=(x*x)%MOD;//这里也要取模，真该死啊啊啊啊啊啊啊啊
    y>>=1;
    }
    return result%MOD;
}
//费马小定理，这里要知道的是，除法和取模是不可以一起用的，
//x/k%MOD是不对的，x*k^(MOD-2)这样是对的，见博客
int inv(int x){
    return quick(x,MOD-2);
}
signed main(){
    int n;
    cin>>n;
    int ans=quick(2,n-1);
    for(int i=1;i<=n;i++){
        ans=ans*(n-i+1)%MOD;
        ans=ans*inv(i)%MOD;
        cout<<ans<<" \n"[i==n];
    }
}

感悟

居然现在才知道吗，有点失败了，果然还是新手阿

// TRAINING LOG · 第 8 / 76 篇训练记录 · 成文于 2026.02.01 · 夜间 21:18