HDU1395 2^x mod n = 1
最新推荐文章于 2021-07-23 14:32:50 发布

ACMerszl 于 2018-07-18 17:10:33 发布
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
题目链接
思路:本来以为如果是偶数就? 奇数就 5 = 2*2 + 1 所以就是 2的4次方 。WA! 例如, 2^x mod 7 = 1. 这样的答案是
7 = 2 * 3 + 1 是6吗? 6的确对,但是要保证最小。所以思路错误。看了题解。了解到费马小定理,还是欧拉定理能够得到奇数必有解。
AC代码:(暴力求解)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
int main() {
int n;
while(~scanf("%d", &n)) {
if(n&1 && n != 1) {
int res = 1, t = 2;
while(t%n != 1) {
t = t*2%n;
res++;
}
printf("2^%d mod %d = 1n", res, n);
} else {
printf("2^? mod %d = 1n", n);
}
}
}
思路:
1. 当n为偶数时,bn + 1(b为整数)是奇数,而2^x是偶数,故 2^x mod n = 1不可能成立;
2. 当n等于1时,不能成立
3. 当n为非1的奇数时,n和2互质,由欧拉定理:若a,n为正整数,且两者互素,则a^phi(n) mod n = 1,其中phi(n)是n的欧拉函数。知2^phi(n) mod n = 1.因此phi(n)必是符合要求的x,但phi(n)未必是最小的,遍历小于其的正整数,逐一试验即可,计算2^x mod n时用快速幂乘。
博客链接
AC代码:
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
int eular(int n) {
int ans = n;
for(int i = 2; i*i <= n; i++) {
if(n % i == 0) {
ans -= ans / i;
while(n % i == 0) {
n /= i;
}
}
}
if(n > 1) ans -= ans / n;
return ans;
}
ll mod_pow(ll x, ll n, ll mod) {
ll res = 1;
while(n > 0) {
if(n&1) res = res * x % mod;
x = x * x % mod;
n >>= 1;
}
return res;
}
int main() {
int n;
while(~scanf("%d", &n)) {
if(n&1 && n != 1) {
int zhi = eular(n);
for(int i = 1; i <= zhi; i++) {
if(mod_pow(2, i, n) == 1) {
printf("2^%d mod %d = 1n", i, n);
break;
}
}
} else {
printf("2^? mod %d = 1n", n);
}
}
}
相关知识
Matlab中的N=size(X,2)是什么意思
设有三个映射如下: (1)f:R→R,f(x)=x; (2)f:Z→N,f(x)
枫树Mod
x^2+y^2=m^2+n^2=1,求mx+ny的最大值
x^2+y^2=9,m^2+n^2=1,求mx+ny的最大值
标函数F(x)=x 1 2 +x 2 2
设二次型f=x 1 2 +x 2 2 +x 3 2 一4x 1 x 2 —4x
素数的判定
matlab程序设计
若x(n)={4,2,3,1}, 0≤n≤3, h(n)={2,4,1},
原文链接: HDU1395 2^x mod n = 1 https://m.huajiangbk.com/newsview1074157.html
| 上一篇: 输出n个格子需要的麦粒数 | 下一篇: qt QFont参数问题 |



