[数论]hdu 2973 YAPTCHA

发表于 | 更新于:
  • 威尔逊定理处理阶乘和除法

题目链接https://vjudge.net/problem/HDU-2973

题意

upload successful
求图上的式子qaq

思路

$(p-1)!\equiv-1(mod\ p)$当且仅当$p$为素数时成立；
当$3n+7$为素数时，$(3n+6)!+1$可记为$m*(3n+7)$，$\lfloor \frac{(3n+6)!}{3n+7} \rfloor$的结果为$m-1$，此时$S{n}=S{n-1}+1$;
当$3n+7$不是素数时，$\lfloor \frac{(3n+6)!+1}{3n+7}\rfloor$和$\lfloor \frac{(3n+6)!}{3n+7} \rfloor$结果相同，此时$S{n}=S{n-1}$;
然后筛法求个3e6+7的素数就行了。

代码qaq

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
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e6+10;
bool vis[maxn];
int prime[maxn];
int isprime[maxn];
int s[maxn];
int f(int n){
    int cnt =0;
    memset(vis,0,sizeof(vis));
    for(int i=2;i<=n;i++){
        if(!vis[i]) prime[cnt++]=i,isprime[i]=1;
        for(int j=0;j<cnt&&i*prime[j]<=n;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
                break;
        }
    }
    return cnt;
}

void init(){
    s[1]=0;
    for(int i=2;i<1e6+3;i++){
        if(isprime[i*3+7]) s[i]=s[i-1]+1;
        else s[i]=s[i-1];
    }
}

int main(){
    f(maxn-1);
    init();
    int t;scanf("%d",&t);
    while(t--){
        int num;scanf("%d",&num);
        printf("%d\n",s[num]);
    }
    return 0;
}