[HDU2588]GCD(欧拉函数)

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


本文章由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\),则$$b$$与$$c$$互质,而可能的$$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