Question

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

#include<iostream>
using namespace std;
int main()
{
int m,n,k=0,i,j,count;
while(cin>>m>>n){
k++;
printf("Case %d:",k);
count=m;
for(i=2;i<=m;i++){
for(j=2;j<=i;j++)
if((i%j==0&&n%j==0)||i%n==0){
count--;
break;
}
}
cout<<count<<endl;
}
return 0;
}

Answer 1

#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;
}

追问

谢谢