流量统计是可以查询到网站来路的关键字里出现了不相关的关键词,南宁网站建站公司,wordpress四级级分类目录,网站建设 腾云求1~N的所有即约分数 公约数求法#xff1a;可以使用欧几里得除法求得公约数 算法原理#xff1a; a,b为两个整数#xff0c;ab a除以b的商q1和余数r1 如果r1为0#xff0c;则最大公约数就为b 如果不为0#xff0c;则继续使用b除以r取商为q2,余r2 如果r2为0#xff0…求1~N的所有即约分数 公约数求法可以使用欧几里得除法求得公约数 算法原理 a,b为两个整数ab a除以b的商q1和余数r1 如果r1为0则最大公约数就为b 如果不为0则继续使用b除以r取商为q2,余r2 如果r2为0则最大公约数是r1 如果不为0则继续使用r2除以r1
递归思想始终是上一次的除数除以上一次的余数然后判断是否本次余数为0否为0则返回除数
gcd(a,b)
return gcd(b,a%b);
当然递归要加终止条件完整版
int gcd(int a,int b )
{
if (b0) return a;return gcd(b,a%b);
}最终代码
#includebits/stdc.h
using namespace std;
int gcd(int a,int b);
signed main()
{int ans0;for(int i1;i2020;i) {for(int j1;ji;j)//if(__gcd(i,j)1) ans;if(gcd(i,j)1) ans;}cout2*ans-1endl;return 0;}
int gcd(int a,int b )
{
if (b0) return a;return gcd(b,a%b);
}
这里最小公倍数就也很好计算了 两个数相乘除以最大公约数就是最小公倍数
改进算法
求即约分数即要求分子与分母互质互为质数。根据数论知识1~n中与n互质的数的个数称为欧拉函数记作phi[n]。 唯一分解定理任何一个数要么本身是质数要么可以分解为有限个质数的乘积。 根据欧拉公式和唯一分解定理可得算法如下
唯一分解定理cpp
//唯一分解定理能够把任意一个数分解成有限个质数的相乘
int getPrime(int p[],int n)
{int k0;//记录质数的个数for(int i2;i*in;i){if(n%i0) p[k]i;//如果能够被除掉说明i就是其一个质数while(n%i0) n/i;//等同于nn/i,出去其重复因子}if(n1) p[k]n;//前面没有一个数满足要求则这个数质数因子只有是n本身了return k;
}求Euler函数 cpp
//求解欧拉函数
int getEuler(int n)
{int phin;int kgetPrime(P,n);for(int i1;ik;i){phiphi-phi/P[i];}return phi;
}全部代码如下
#includebits/stdc.h
using namespace std;
int P[2020]{0};
//唯一分解定理能够把任意一个数分解成有限个质数的相乘
int getPrime(int p[],int n)
{int k0;//记录质数的个数for(int i2;i*in;i){if(n%i0) p[k]i;//如果能够被除掉说明i就是其一个质数while(n%i0) n/i;//等同于nn/i,出去其重复因子}if(n1) p[k]n;//前面没有一个数满足要求则这个数质数因子只有是n本身了return k;
}
//求解欧拉函数
int getEuler(int n)
{int phin;int kgetPrime(P,n);for(int i1;ik;i){phiphi-phi/P[i];}return phi;
}int main()
{int ans0;int ans10;ansgetPrime(P,2020); for(int i1;i2020;i)ans1getEuler(i);cout2*ans1-1endl;return 0;
}
