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
Sample Output
题意：给定一个数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的素因子，如果等于就满足，否则不满足
hdu4910（米勒罗宾）,布布扣,bubuko.com
hdu4910（米勒罗宾）
原文：http://blog.csdn.net/cq_phqg/article/details/38512625
