c语言题 求助

这道题中n的最大取值为10⁹，所以直接遍历依次判断再求和会超时

注意到1~n所有数的和容易求得，为sum=n(n+1)/2

可以采用容斥原理，即先求出总体的和sum

减去其中所有a的倍数的和suma和b的倍数的和sumb

再加上所有同时能被a和b整除的数的和sumab即可

1~n中能被a整除的最大数为[n/a]*a，能被b整除的最大数为[n/b]*b（[ ]表示下取整）

又a和b互质，所以能同时被a和b整除的数为[n/(a*b)]*(a*b)

再通过求和公式就可以直接计算出suma、sumb和sumab

具体代码如下：

#include

typedef long long int ll; // 定义长整型别名为ll，防止溢出

int main() {

    int n, a, b;

    scanf("%d %d %d", &n, &a, &b);

    ll sum = (ll)n * (n + 1) / 2; // 1~n所有数之和

    int ka = n / a, kb = n / b, kab = n / (a * b);

    ll suma = (ll)a * ka * (ka + 1) / 2; // a的倍数之和

    ll sumb = (ll)b * kb * (kb + 1) / 2; // b的倍数之和

    ll sumab = (ll)a * b * kab * (kab + 1) / 2; // ab的倍数之和

    printf("%lld\n", sum - suma - sumb + sumab);

    return 0;

}

运行结果如下：

符合示例输出，望采纳~

int i，s=0;
for(i=1;i〈=n;i十十)
{if((i%a)&&(i%b))s十=i;}
printf("%d\n"，s);