首页 > 代码库 > HDU 4910 Problem about GCD(米勒拉宾)
HDU 4910 Problem about GCD(米勒拉宾)
HDU 4910 Problem about GCD
题目链接
题意:给定一个数字,求出1 - n之间与他互质的数的乘积mod n
思路:看了网上别人找出来的规律,原文链接
然后由于这题的n很大,也没法直接判定,可以这样搞,先去试10^6以内的素数,判断可不可以,如果不行,再利用米勒拉宾判下是否是素数,如果不是的话,把这个数字开根在平方,判断是不是完全平方数,这样做的原因是数字最大10^18,如果没有10^6以内的质因子,又不是质数的话,那么他最多只能包含2个质因子了,那么如果他不是一个完全平方数的话,那么就肯定不是了
代码:
#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> typedef long long ll; const int N = 1000005; ll n, prime[N]; int vis[N], pn; ll mul(ll a, ll b, ll mod) { ll ret = 0; while (b > 0) { if (b&1) ret = (ret + a) % mod; b >>= 1; a = (a<<1) % mod; } return ret; } ll pow_mod(ll x, ll k, ll mod) { ll ans = 1; while (k) { if (k&1) ans = mul(ans, x, mod); x = mul(x, x, mod); k >>= 1; } return ans; } bool mlrb (ll n) { if (n < 2) return false; if (n == 2) return true; if (n % 2 == 0) return false; for (int i = 0; i < 20; i++) { ll a = rand() % (n - 1) + 1; if (pow_mod(a, n - 1, n) != 1) return false; } return true; } void get_table() { pn = 0; for (ll i = 2; i < N; i++) { if (vis[i]) continue; prime[pn++] = i; for (ll j = i * i; j < N; j += i) vis[j] = 1; } } bool check(ll n) { for (int i = 1; i < pn; i++) { if (n % prime[i] == 0) { ll tmp = n; while (tmp % prime[i] == 0) tmp /= prime[i]; if (tmp == 1) return true; else break; } } if (mlrb(n)) return true; ll m = (ll)sqrt(n * 1.0); if (m * m == n) return true; return false; } bool judge(ll n) { if (n == 1 || n == 2 || n == 4) return true; if (n % 4 == 0) return false; if (n % 2 && check(n)) return true; if (n % 2 == 0 && check(n / 2)) return true; return false; } int main() { get_table(); while (~scanf("%I64d", &n) && n != -1) { if (judge(n)) printf("%I64d\n", n - 1); else printf("1\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。