首页 > 代码库 > hdu4910（米勒罗宾）

hdu4910（米勒罗宾）

2024-07-17 03:13:54   221人阅读

Problem about GCD

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 522    Accepted Submission(s): 86


Problem Description
Given integer m. Find multiplication of all 1<=a<=m such gcd(a, m)=1 (coprime with m) modulo m.
 

Input
Input contains multiple tests, one test per line.
Last line contains -1, it should be skipped.

[Technical Specification]
m <= 10^18
 

Output
For each test please output result. One case per line. Less than 160 test cases.
 

Sample Input
1
2
3
4
5
-1
 

Sample Output
0
1
2
3
4

题意：给定一个数n，求所有小于等于n且与n互素的数的乘积再mod n

思路：打表可以发现如下规律，只有当n是1,2,4或者只有一种质因子的时候答案为n-1，其它都为1，如果n是偶数，就把n除以2以后再判断，如果n小于1e6则可以直接判断，如

果n很大，就先用1e6以下的素数去整除，看能不能判断出来，如果还不能，就用米勒罗宾判断n是否为素数，如果是，那么n满足，如果不是就将n开方以后再平方看是否等于

n，因为n是小于1e18的，所以n不可能有三个大于1e6的素因子，如果等于就满足，否则不满足

<script src="https://code.csdn.net/snippets/448393.js" type="text/javascript"></script>


联系
我们