UVA1434 YAPTCHA

题目链接

题目分析

令 $d=3k+7，d\geq7$ ，则原式可变为

$$\sum^n_{i=1} {\left [ \frac{(d-1)!+1}{d}-\left[ \frac{(d-1)!}{d}\right] \right ] }$$

当 d 为素数时，由威尔逊定理可知，$\frac{(d-1)!+1}{d}$ 必定是整数，且 $\left[ \frac{(d-1)!}{d}\right]=\frac{(d-1)!+1}{d}$-1，即 d 为素数时 $\left [ \frac{(d-1)!+1}{d}-\left[ \frac{(d-1)!}{d}\right] \right ] =1$

当 d 为非素数时，$\left [ \frac{(d-1)!+1}{d}-\left[ \frac{(d-1)!}{d}\right] \right ] = \left [ \frac{(d-1)!\ (\ mod\ d)+1}{d} \right ]=0 $

则仅需预处理 $[7,3000007]$ 中的素数即可

代码实现

#include <bits/stdc++.h>
using namespace std;
const int maxn=3e6+9;
int prime[maxn];
bool vis[maxn];
int Ans[maxn];
int cnt=0;
void Euler_prime(int n)
{
	for(int i=2; i<=n; ++i)
	{

		if(!vis[i])
		{
			prime[cnt++]=i;    //vis[i]置为true或不置true都可以
			vis[i]=true;
			if((i-7)%3==0&&i>7)
				Ans[(i-7)/3]++;
			
		}
		for(int j=0; j<cnt; ++j)
		{
			if(i*prime[j]>n)//判断是否越界
				break;
			vis[i*prime[j]]=true;//筛数
			if(i%prime[j]==0)//时间复杂度为O(n)的关键！
				break;
		}
		if((i-7)%3==0&&i>7)
			Ans[(i-7)/3+1]=Ans[(i-7)/3];

	}
}
int main()
{
	Euler_prime(maxn);
	int T,t;
	cin>>T;
	for(int i=1; i<=T; ++i)
	{
		cin>>t;
		cout<<Ans[t]<<endl;
	}
	return 0;
}