程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA 1434 - YAPTCHA(數論)

UVA 1434 - YAPTCHA(數論)

編輯:C++入門知識

UVA 1434 - YAPTCHA

題目鏈接

題意:求出題目中那個公式的答案

思路:
當3?k+7非素數的時候,那麼(3?k+6)!(因為必然能找到兩個因子相乘)
所以原式為0

當3?k+7為素數的時候,根據威爾遜定理,((3?k+6)!+1)%(3?k+7)==0,因此原式可以轉化為[x - (x - 1)] = 1

因此問題轉化為只要判斷3 * k + 7是不是素數,那麼就很好辦了,預處理出素數表,再預處理出答案即可

代碼:

#include 
#include 

const long long N = 1000005;

bool ispri[N * 3];
int ans[N], t, n;

int main() {
    for (long long i = 2; i < N * 3; i++) {
	if (ispri[i]) continue;
	for (long long j = i * i; j < N * 3; j += i)
	    ispri[j] = true;
    }
    for (int i = 2; i < N; i++)
	ans[i] = ans[i - 1] + (!ispri[3 * i + 7]);
    scanf("%d", &t);
    while (t--) {
	scanf("%d", &n);
	printf("%d\n", ans[n]);
    }
    return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved