HOJ 2588 GCD（约数，欧拉函数）

约数，欧拉函数
题目意思：
给出 n, m 两个数（1 <= m <= n < 1e9）, 求有多少个数 x ，满足 1 <= x <= n, 使得 gcd(x, n) >= m

本题要点：
1、先求出 gcd(x, n)（假设等于 g）， 那么 gcd(x / g, n / g) = 1, 联想到 欧拉函数
x / g <= n / g, 欧拉函数 phi(n / g) 表示 小于 n / g 的数，有多少个与 之互质的。
2、解答：
先求出 n的所有的约数 y，看看那些约数大于m，然后 用 n 除以 y ， 得到 n / y,
然后计算 phi(n / y), 全部累计起来就是答案。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int T, n, m;int phi(int x)	//求x 的欧拉函数
{
    int ans = x, k = x;for(int i = 2; i * i <= k; ++i){
    if(x % i == 0){
    ans = ans / i * (i - 1);while(x % i == 0)x /= i;}}if(x > 1)ans = ans / x * (x - 1);return ans;
}void solve()
{
    int ans = 0;for(int i = 1; i * i <= n; ++i)	//只存放大于m的约数{
    if(n % i == 0){
    if(i >= m)ans += phi(n / i);if(i != n / i && n / i >= m){
    ans += phi(i);}}}printf("%d\n", ans);
}int main()
{
    scanf("%d", &T);while(T--){
    scanf("%d%d", &n, &m);	solve();}return 0;
}/* 3 1 1 10 2 10000 72 *//* 1 6 260 */