首页 > 代码库 > hdu4910（米勒罗宾）
hdu4910（米勒罗宾）
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
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>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。