跳到主要内容

威尔逊定理

威尔逊定理：​

(p−1)!≡−1( mod p) 是 p 为质数的充分必要条件 (p-1) ! \equiv-1(\bmod p) \text { 是 } p \text { 为质数的充分必要条件 } 推论：

  • 若pp是质数,则(p−1)!+1≡0( mod p)(p-1)!+1\equiv 0(\bmod p)
  • 若pp是大于4的合数，则(p−1)!≡0( mod p)(p-1)! \equiv 0(\bmod p)

题目​

已知n<=106n<=10^6，求Sn=∑k=1n[(3k+6)!+13k+7−[(3k+6)!3k+7]]S_{n}=\sum_{k=1}^{n}\left[\frac{(3 k+6) !+1}{3 k+7}-\left[\frac{(3 k+6) !}{3 k+7}\right]\right][]是下取整

思路​

令p=3k+7p=3k+7,求和项变为：[(p−1)!+1p−[(p−1)!p]]\left[\frac{(p-1) !+1}{p}-\left[\frac{(p-1) !}{p}\right]\right] 若pp为质数，则(p−1)!+1≡0( mod p)(p-1)!+1\equiv 0(\bmod p)，即前一项为整数，后一项肯定比前一项少1，则[(p−1)!+1p−[(p−1)!p]]=1\left[\frac{(p-1) !+1}{p}-\left[\frac{(p-1) !}{p}\right]\right]=1 若pp是合数，p>=10p>=10，则(p−1)!≡0( mod p)(p-1)! \equiv 0(\bmod p),则[(p−1)!+1p−[(p−1)!p]]=0\left[\frac{(p-1) !+1}{p}-\left[\frac{(p-1) !}{p}\right]\right]=0 因此只需要统计1−n1-n中都合法质数即可，合法质数的样子为p=3k+7p=3k+7

代码​

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define debug(x) cout<<"a["<<x<<"]="<<a[x]<<endl;
#define pr(x) cout<<x<<endl;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 3e6 + 10;

int n;
int primes[N];
bool st[N];
int s[N];

// 3k+7
void get_prim(){
    for(LL i = 2; i < N; ++i)
        if(!st[i]){
            if((i-7)%3 == 0)
                primes[(i-7)/3] = 1;
            for(LL j=i*i; j<N; j+=i)
                st[j] = 1;
        }
}


int main() {
    IOS;
#ifndef ONLINE_JUDGE
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.in", "r", stdin);
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.out", "w", stdout);
#endif
    get_prim();
    for(int i=2;i<N;i++)
        s[i]=s[i-1]+ primes[i];
    int t;
    cin>>t;
    while (t--){
        cin>>n;
        pr(s[n])
    }

    return 0;
}

0%