做衣服网站,优化什么,随州网站seo,wordpress 适应手机互质#xff1a;
互质是公约数只有1的两个整数#xff0c;叫做互质整数。公约数只有1的两个自然数#xff0c;叫做互质自然数#xff0c;后者是前者特殊情况。
#xff08;1和-1与所有整数互质#xff0c;而且它们是唯一与0互质的整数#xff09;
互质的判断方法
互质是公约数只有1的两个整数叫做互质整数。公约数只有1的两个自然数叫做互质自然数后者是前者特殊情况。
1和-1与所有整数互质而且它们是唯一与0互质的整数
互质的判断方法
1两个数互质的情况
1两个不同的质数是互质的。
2较大数是质数的两个数是互质数
3相邻的两个自然数是互质数
4相邻的两个奇数是互质数
5最大公约数是1两个数互质
2三个或三个以上自然数互质有两种不同的情况
一种是这些成互质数的自然数是两两互质的。如235
一种不是两两互质的如689 欧拉函数
一般记作是指中与互质的数的个数
将看成质因数的乘积形式
其中代表各个质因子代表各个质因子的质指数。
那么 step1
采用分解质因数的方法分别求出N质因数乘积式中的每一个质因数p_n
分解质因数http://t.csdnimg.cn/Tmf0G
step2
每第一次遇到一个质因数就套用公式 res res/i*(i-1)
注意因为公式中不涉及到任何一个质因数的指数所以 res res/i*(i-1) 不应该放在while(x%i0) 之中
step3
输出结果 题目如下
给定 n 个正整数 ai请你求出每个数的欧拉函数。
输入格式
第一行包含整数 n。
接下来 n 行每行包含一个正整数 ai。
输出格式
输出共 n 行每行输出一个正整数 ai 的欧拉函数。
数据范围
1≤n≤100 1≤ai≤2×109 代码如下
#includeiostream
#includecstringusing namespace std;int n;int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin n;while(n--){int x;cin x;int res x;//注意res的初始值是x因为在公式的一开始是N本身for (int i 2 ;ix/i;i){if (x % i 0){res res/i * (i-1);//这里注意要先进行除法再进行乘法//不然会爆掉int//爆掉int后取值就是超过int最大值的部分如超过int最大值1//那么爆掉int后的取值就是1while(x % i 0)x x/i;}}if (x 1)res res/x * (x-1);cout res endl;}return 0;
} 1公式推导 2要先写除法再写乘法 res res/i * (i-1) res res/i*(i-1) 和 res res*(1-1/i) 是一样的不过是前者先进行了除法后者先进行了乘法 3res res/i*(i-1)不应放在while(x%i 0)之中
因为欧拉公式中不涉及到任何质因数的指数。
如果将 res res/i*(i-1) 放到 while(x%i0) 之中面对一个质因数的指数是2那么res最后的答案中就会乘了两次
放进 while(x%i0) 中质因数的指数就会对结果产生影响
