A.Cows and Primitive Roots
题意,给定一个素数p(2<p>2000),要求1<=x<p,x-1,x^2-1,..x^(p-2)-1都不能被p整除,但x^(p-1)-1能整除p,要统计这样的x有多少个
思路,由于此题p值比较小,于是我是用快速幂取模(经典分治算法),直接计算幂,看是不是满足条件
#include<iostream>
#include<algorithm>
#include<list>
#include<cstdio>
#include<stack>
#include<string>
#include<cstring>
#define MAXN 100005
#define debug_cout(x,y) cout<<x<<":"<<y<<endl
using namespace std;
long exp_mod(long a,long n,long b)
{
long long t;
if(n==0) return 1%b;
if(n==1) return a%b;
t=exp_mod(a,n/2,b);
t=t*t%b;
if((n&1)==1) t=t*a%b;
return t;
}
int main(){
int p;
cin>>p;
int x,i,flag,ans=0;
for(x=1;x<p;x++){
flag =1;
for (i=1;i<p-1;i++)
{
int t = exp_mod(x,i,p);
t = (t+p-1) % p;
if (t==0) {
flag = 0;break;
}
}
if (flag==1 && ((exp_mod(x,p-1,p)+p-1)%p)==0)
ans++;
}
cout<<ans;
return 0;
}
算法复杂度为O(P^2*logP)
后面发现,完全没必要每个p都快速幂算一次,不需要快速幂求模,因为x的1~p-1次幂模p可以直接一个for迭代计算出来,算法复杂度O(P^2)
看了tutorial这道题还有O(sqrt(P))的解法,没想明白为什么
大概意思
费马小定理是数论中的一个重要定理,其内容为: 假如p是质数,且(a,p)=1,那么
a^(p-1) ≡1(mod p) 假如p是质数,且a,p互质,那么 a的(p-1)次方除以p的余数恒等于1
对于这道题只要找到与p-1互质的数的个数,就能满足那两个条件,而找与p-1互质数的个数可以用欧拉函数(先求整除p-1的质因子,再带入公式
分享到:
相关推荐
题意: 给了一堆楼 要求 不能存在 i < j> aja_jaj < aka_kak 的情况 不一定非要挨着 楼高有限制 不得超过mim_imi 官方题解是 单调栈 正着一遍 反着一遍就可以了 正着:dp[i]前i个保持递增序列的最大前缀...
Bulls and Cows,在linux下编译成功,完整程序
bulls_and _cows.py
测试数据
poj 2430 Lazy Cows.md
玩家(计算机和你)使用从 1 到 9 的数字想出一个秘密的三位数字,没有任何重复。 游戏的目标是先轮流猜出对手的秘密号码。 猜中的奶牛数是猜中的数字和对手的秘密数字中但位置不同的数字的数量。...
USACO题目Milking Cows及代码解析
带有排行榜的 Bulls and Cows 游戏的 node.js 实现 分叉了优秀的: : 安装 下载并安装 node.js 和 npm 和 mongodb 跑步 转到您将克隆此 repo 的目录并运行: git clone ...
cows_and_bulls 经典的牛与牛游戏。 现场演示: : Bulls and Cows(也称为Cows and Bulls或Pigs and Bulls)是供两个或两个以上玩家使用的打破常规的思维或纸和铅笔游戏,早于商业发行的棋盘游戏Mastermind。
Bulls-and-Cows-game
The cows in farmer John's herd are numbered and branded with consecutive integers from 1 to N (1 ,000,000). When the cows come to the barn for milking, they always come in sequential order from 1 to N...
Effect of mastitis on milk of hybrid Sudanese cows,Ali Ahmed Hassabo,,This research aims to study the phenomenon of spreading mastitis among the Sudanese crossbred dairy cows fresian X Kenana (FXK)...
P8898 [USACO22DEC] Feeding the Cows B 题解.docx
这是一个互动式的网页,使用HTML , CSS和JavaScript制作而成,是原始的Bulls and Cows游戏的数字版本。 使用的工具和语言: 下载和用法: 可以从github Web界面将代码下载为压缩的zip文件。 还可以使用以下方法...
bulls_and_cows
牛与牛Android中的代码破解思维游戏。要了解有关游戏及其玩法的更多信息: 先决条件Android SDK v27 Android构建工具v27.1.0 Android支持存储库v27.1.0运行应用本示例使用Gradle构建系统。 要构建此项目,请使用...
Cows in the us
母牛和公牛 猜词游戏 奶牛的数量是在错误位置正确猜出的字母的数量。 多头的数量是正确位置上正确猜测的字母的数量。 在每一轮中,您都可以输入一个有效的英语单词作为猜测。 请记住,您的单词应该包含所有独特的...
公牛和牛 公牛和牛游戏说明: 每个游戏都以随机代码和4种不同的颜色开始,玩家的目标是最多显示7个回合。 玩家每转一圈都会猜出4种颜色的代码,按下“提交”按钮时,玩家会得到提示,提示有错误。...