一道简单的C++问题，程序是对的，但是运行太慢，求优化

#include <iostream>

using namespace std

int gcd(int a, int b)

{

    if (!b)

        return a

    else

        return gcd(b, a % b)

}

int main()

{

    int m,n,k=0,count

    while (cin >> m >> n)

    {

        k++

        printf("Case %d:", k)

        count = m

        for (int 升埋和i = 2 i <= m i++)

        {

            if (gcd(i, n) != 1 || gcd(i, n) == n)

                --count

        }

        cout<<count<<endl

    }

    return 0

}

以上液枝代码做到了O(m*logn)

如果希望时间效率更优秀的话，用容吵盯斥原理可以做到O(k*2^k)，其中k是m的质因子个数

容斥原理的代码我也贴上来吧

#include <iostream>

using namespace std

typedef long long LL

const int maxn = 50

LL prime[maxn]

LL make_ans(LL num, int m)

{

LL ans = 0, tmp, flag

for (int i = 1 i < (LL)(1 << m) i++)

{

tmp = 1, flag = 0

for (int j = 0 j < m j++)

if (i & ((LL)(1 << j)))

flag++, tmp *= prime[j]

if (flag & 1)

ans += num / tmp

else

ans -= num / tmp

}

return num - ans

}

int main()

{

    int m, n, k = 0, count

    while (cin >> m >> n)

    {

        k++

        printf("Case %d:", k)

        int M = 0, flag = (n == 1)

        for (int i = 2 i * i <= n i++)

if (n && n % i == 0)

{

prime[M++] = i

while (n && n % i == 0)

n /= i

}

        if (n > 1)

prime[M++] = n

        count = (flag ? 1 : make_ans(m, M))

        cout << count << endl

    }

    return 0

}

首先氏升，查看一下本机的配置，是不是电脑本身的原因。

其次，你所哪拍谓的慢，是执行的慢，还是结果出现的慢，一般在windows下，编译器会生成相应的.exe程序，不妨运行一下试一试。另外，你执行的时候，那面会有一定的反应时间。再不行的话，换个歼缓老编译器好了。

---