首页 > 代码库 > hdu 4910 Problem about GCD(数论)
hdu 4910 Problem about GCD(数论)
题目连接:hdu 4910 Problem about GCD
题目大意:给定M,判断所有小于M并且和M互质的数的积取模M的值。
解题思路:有个数论的结论,若为偶数,M=M/2. 可以写成M=pk,即只有一种质因子时,答案为M-1,否则为1.特殊情况为4的倍数,不包括4.
首先用1e6以内的素数去试除,如果都不可以为p,那么对大于1e6的情况判断一下是否为素数,是素数也可以(k=1),否则开方计算,因为M最大为1e18,不可能包含3个大于1e6的质因子。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime> // possible need;
#include <cstdlib> // possible need;
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long type;
type mul_mod (type a, type b, type mod) {
type ret = 0;
while (b) {
if (b&1)
ret = (ret + a) % mod;
a = (a + a) % mod;
b >>= 1;
}
return ret;
}
type pow_mod (type a, type n, type mod) {
type ans = 1;
while (n) {
if (n&1)
ans = mul_mod(ans, a, mod);
a = mul_mod(a, a, mod);
n >>= 1;
}
return ans;
}
bool miller_rabin(type n) {
if (n < 2)
return false;
srand(time(0));
for (int i = 0; i < 20; i++)
if (pow_mod(rand() % (n-1) + 1, n-1, n) != 1)
return false;
return true;
}
typedef long long ll;
const int maxn = 1e6;
bool vis[maxn+5];
int np, pri[maxn+5];
void prime_table (int n) {
np = 0;
memset(vis, 0, sizeof(vis));
for (int i = 3; i <= n; i += 2) {
if (vis[i])
continue;
pri[np++] = i;
for (int j = i * 2; j <= n; j += i)
vis[j] = 1;
}
}
bool judge (ll M) {
if (M % 2 == 0)
M /= 2;
for (int i = 0; i < np; i++) {
ll tmp = M;
while (tmp % pri[i] == 0)
tmp /= pri[i];
if (tmp == 1)
return true;
}
if (M <= 1000000LL)
return false;
if (miller_rabin(M))
return true;
ll x = sqrt(M+0.0);
while (x * x < M)
x++;
if (x * x != M)
return false;
if (miller_rabin(x))
return true;
return false;
}
int main () {
ll M;
prime_table(maxn);
//srand(time(0));
while (scanf("%I64d", &M) == 1 && M != -1) {
if (M == 1 || M == 2 || M == 4 || judge(M))
printf("%I64d\n", M-1);
else
printf("1\n");
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。