[HDU2588]GCD(欧拉函数)

发布于 2018-01-11  9 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[HDU2588]GCD(欧拉函数)

Description

The greatest common divisor GCD(a,b) of two positive integers a and b,sometimes written (a,b),is the largest divisor common to a and b,For example,(1,2)=1,(12,18)=6.
(a,b) can be easily found by the Euclidean algorithm. Now Carp is considering a little more difficult problem:
Given integers N and M, how many integer X satisfies 1<=X<=N and (X,N)>=M.

Http

HDU

Tag

欧拉函数

题目大意

给定数\(N\),求满足\(gcd(x,N)>=M\)的\(X\)的数量

解决思路

考虑\(N=a*b\),若\(gcd(N=a*b,a*c)==a\),则bc互质,而可能的c的数量就是与b互质的数的个数,即为\phi(b),所以可以考虑枚举N的因子a,求\phi(a)之和。
但是考虑到N的范围,直接枚举会超时。因为对于N的因数a,一定存在一个对应的因数b使得N=a*b,所以我们只需要枚举到\sqrt{n}即可,注意判断n为完全平方数的情况,此时\sqrt{n}只能算一遍

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[HDU2588]GCD(欧拉函数)


HNCJ OIer 一枚