对每组数据输出一行,形如 "Case #i: ans"(不含引号)
ans 为区间 [L,R] 中所有反立方数的平方和
- 2
- 1 5
- 1 10
- Case #1:55
- Case #2:321
容斥原理。
预处理 10^6 以内的质数,作为立方数的原数。
暴力搜索 10^6 以内质数的组合,注意保证没有重复的数字,比如 2*2 不合法,因为 2*2 的倍数包含在 2 的倍数里;以及重复的组合,比如 2*3*5 和 3*2*5 是重复的。
设 sum=(1^3)^2+(2^3)^2+...+(n^3)^2
设 cnt 为立方数的平方和。对于枚举到的素数组合,若组合数的个数为奇数,则 cnt 加上该组合数所有倍数的平方和,用平方和公式计算;若为偶数,则减去。
根据容斥原理,n 以内的反立方数的平方和 ans=sum-cnt。
答案为 ans(r)-ans(l-1)。
需要注意 MOD 的使用,很容易遗漏 MOD 导致爆 long long。
另外程序中会用到 (A/B)%MOD, 根据费马小定理,(A/B)%MOD=A*B^(MOD-2)。
来源: http://www.bubuko.com/infodetail-2065120.html