首页 > 代码库 > uva 1434 - YAPTCHA(数论)
uva 1434 - YAPTCHA(数论)
题目链接:uva 1434 - YAPTCHA
题目大意:给定n和k,求题目中给定的式子S(n)。
解题思路:威尔逊定理,x为素数时有,((x?1)!+1)%x==0,所以对于本题,如果3*k+7为素数的话,[(3k+6)!+1(3k+7?[(3k+6)!3k+7]]=1
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 1e6;
int ans[maxn+5], vis[maxn*4+5];
void primeTable (int n) {
memset(vis, 0, sizeof(vis));
for (int i = 2; i <= n; i++) {
if (vis[i])
continue;
for (int j = 2 * i; j <= n; j += i)
vis[j] = 1;
}
}
int main () {
primeTable(maxn*4);
ans[1] = 0;
for (int i = 2; i <= maxn; i++)
ans[i] = ans[i-1] + (vis[3*i+7] ? 0 : 1);
int cas, n;
scanf("%d", &cas);
while (cas--) {
scanf("%d", &n);
printf("%d\n", ans[n]);
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。