博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hdu5391Zball in Tina Town
阅读量:6340 次
发布时间:2019-06-22

本文共 727 字,大约阅读时间需要 2 分钟。

//求(n-1)!%n//n 为合数,答案为0,n为素数 。 威尔逊定理可得//判定一个自然数是否为素数的充分必要条件。

即:当且仅当p为素数时:( p -1 )! ≡ -1 ( mod p ) //答案为(n-1) 注意4的时候 #include<iostream> #include<cstdio> #include<cstring> using namespace std ; const int maxn = 1e5 +10 ; int len ; int isp[maxn] , a[maxn] ; void get_prime() { memset(isp , 0 , sizeof(isp)) ; len = 0 ; for(int i = 2;i < maxn;i++) { if(isp[i])continue ; a[++len] = i ; for(int j = i ;j < maxn;j+=i) isp[j] = 1 ; } } int main() { int n , t ; get_prime() ; scanf("%d" , &t) ; while(t--) { scanf("%d" , &n) ; if(n == 4) { puts("2") ; continue ; } int flag = 0 ; for(int i = 1;i <= len;i++) if(a[i]*a[i] > n)break; else if(n%a[i] == 0) { flag = 1; break; } if(flag)puts("0"); else printf("%d\n" , n-1) ; } return 0 ; }

转载地址:http://imhoa.baihongyu.com/

你可能感兴趣的文章
Vue过滤器
查看>>
linux下库的使用
查看>>
一道面试题引发的关于程序设计的想法
查看>>
2019春第二次课程设计实验报告
查看>>
express入门
查看>>
Codeforces 535D - Tavas and Malekas
查看>>
2017-2018 ACM-ICPC, Asia Tsukuba Regional Contest
查看>>
JS 小总结
查看>>
hihocoder [Offer收割]编程练习赛8
查看>>
[CF98E]Help Shrek and Donkey
查看>>
property函数
查看>>
数论 - 组合数学 + 素数分解 --- hdu 2284 : Solve the puzzle, Save the world!
查看>>
XPath语法
查看>>
linux脚本实现递归阶乘
查看>>
JSON转XML
查看>>
c#典型排序方法总结
查看>>
pkcs1与pkcs8格式RSA私钥互相转换
查看>>
.Net 从零开始构建一个框架之基本实体结构与基本仓储构建
查看>>
C#核编之内建数据类型
查看>>
Oracle运算符收录(易忘记,但是又很重要的运算符)
查看>>