POJ-3641 Pseudoprime numbers---快速幂
2024-09-28 21:03:01
题目链接:
https://vjudge.net/problem/POJ-3641
题目大意:
问p是不是伪素数。伪素数条件:①p不是素数。② ap = a (mod p)。
思路:
直接快速幂模板+素数判断
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<cmath>
using namespace std;
typedef pair<int, int> Pair;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = +;
int T, n, m;
ll pow(ll a, ll b, ll m)
{
ll ans = ;
while(b)
{
if(b & )ans = (ans % m) * (a % m) % m;
b /= ;
a = (a % m) * (a % m) % m;
}
ans %= m;
return ans;
}
bool noprime(int x)
{
for(int i = ; i <= (int)sqrt(x + 0.5); i++)
{
if(x % i == )return true;
}
return false;
}
int main()
{
int p, a;
while(cin >> p >> a && (p + a))
{
if(noprime(p) && pow(a, p, p) == a)cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
}
最新文章
- iOS---正确使用NSNotification对象
- @RenderBody、@RenderSection、@RenderPage、Html.RenderPartial、Html.RenderAction的作用和区别
- JAX-WS服务端及客户端
- LR12.53—第6课:运行负载测试
- 【CQgame】[下一百层] [Down]
- cookies,sessionStorage和localStorage的区别
- Chrome 消息传递机制
- 【转】Solr安全设置——对外禁用管理后台
- Dom4j
- Jquery如何获得<;iframe>;嵌套页面中的元素
- 支付宝openssl漏洞肆虐 互联网巨头称目前已修复
- 利用python建表
- JDBC增强
- GNU自动补全模块readline解析
- POJ1611 The Suspects (并查集)
- GetLastError() 返回值含义
- cocos2d windows游戏平台搭建
- Android 监听 ScrollView 滑动到最底部。
- JS中UTF-8和UTF-16互转
- jQuery动态控制下拉列表的被选项[转]