Zball in Tina Town(数论规律题+特判+较大数判是否为素数的正确
发布时间:2020-12-14 02:24:38 所属栏目:大数据 来源:网络整理
导读:Link:http://acm.hdu.edu.cn/showproblem.php?pid=5391 Zball in Tina Town Time Limit: 3000/1500 MS (Java/Others)????Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 138????Accepted Submission(s): 98 Problem Description Tina T
Link:http://acm.hdu.edu.cn/showproblem.php?pid=5391 Zball in Tina TownTime Limit: 3000/1500 MS (Java/Others)????Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 138????Accepted Submission(s): 98
Problem Description
Tina Town is a friendly place. People there care about each other.
Tina has a ball called zball. Zball is magic. It grows larger every day. On the first day,it becomes?
?
Input
The first line of input contains an integer?
The following?
?
Output
For each test case,output an integer representing the answer.
?
Sample Input
?
Sample Output
?
Source
BestCoder Round #51 (div.2)
?
这题就是求?(n?1)!??mod??n 如果n为合数,显然答案为0. 如果n为素数,那么由威尔逊定理可得答案为?n?1 注意有个trick为?n?= 4 注意:输入的n比较大,要先打素数表再判是否为素数才不会TLE!!! AC code:
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<queue> #include<math.h> #include<vector> #include<map> #include<set> #include<cmath> #include<string> #include<algorithm> #include<iostream> #define LL long long #define MAXN 1000010 using namespace std; const int INF=0x3f3f3f3f; const int N = 100005; const int MOD = 9901; LL n,ans; bool prime[N]; int p[N];//保存素数 int cnt; void isprime()//素数筛选 { cnt = 0; memset(prime,true,sizeof(prime)); for(int i=2; i<N; i++) { if(prime[i]) { p[cnt++] = i; for(int j=i+i; j<N; j+=i) prime[j] = false; } } } bool Judge(LL A)//判断是否为素数,是素数则返回true { for(int i=0; p[i]*p[i] <= A; i++) { if(A % p[i] == 0) { return false; } } return true; } int main() { //freopen("D:in.txt","r",stdin); int t; isprime(); scanf("%d",&t); while(t--) { scanf("%I64d",&n); if(n==4)//特判 { printf("2n"); } else if(!Judge(n)) { printf("0n"); } else { printf("%I64dn",n-1); } } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |