欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU-2588-GCD

程序员文章站 2022-06-07 21:47:32
...

ACM模版

描述

HDU-2588-GCD

题解

枚举 N 的大于等于 M 的约数 x,这样,gcd(N,x)M,最后的结果为所有 N/x 的欧拉函数之和。

y=N/x,欧拉函数是小于 y 并且与 y 互质的数的个数,这样 gcd(xpi,N) 依然是等于 x 的,这样就能避免重复计算。

代码

#include <stdio.h>
#include <math.h>

int Euler(int n)
{
    if (n == 1)
    {
        return 1;
    }

    int x = 2, m = n, tmp = (int)sqrt(n);
    while (x <= tmp)
    {
        if (m % x == 0)
        {
            n -= n / x;
            while (m % x == 0)
            {
                m /= x;
            }
            tmp = (int)sqrt(m);
        }
        x++;
    }
    if (m != 1)
    {
        n -= n / m;
    }
    return n;
}

int solve(int n, int m)
{
    int tmp = sqrt(n), ans = 0;
    for (int i = 1; i <= tmp; i++)
    {
        if (n % i)
        {
            continue;
        }

        if (i >= m && i != tmp)
        {
            ans += Euler(n / i);
        }
        if (n / i >= m)
        {
            ans += Euler(i);
        }
    }

    return ans;
}

int N, M;

int main()
{
    int T;
    scanf("%d", &T);

    while (T--)
    {
        scanf("%d%d", &N, &M);
        printf("%d\n", solve(N, M));
    }

    return 0;
}
相关标签: 欧拉函数

推荐阅读