題意：定義SOD(n)=n除去1和自身的所有因數的和，CSOD(n)為ΣSOD(i),1<=i<=n。T (≤ 1000)組數據，求CSOD(n),(0 ≤ n ≤ 2 * 10⁹)

?

對于不同的數m，m=a*b,a<=b；枚舉a，判斷不大于n的中有哪些可以寫成m=a*b的，把a和b加到答案上。復雜度是O(√n)

如何維護答案呢？

舉例子，作為a出現的3有多少次呢？是n／3 * 3嗎？并不是。要注意到我們要求a<=b，那么從m=9開始，3才會作為a出現，而3，6中的因數3并不作為a對答案貢獻。所以ans +=?(n / i - i + 1) * i;

a為一個數時，對應的b成等差數列，最大值是n / i,最小值是a+1，(注意m=a*a時，a只能算一次貢獻， 所以這里不是a）

1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cmath> 5 #define INF 0x3f3f3f3f 6 using namespace std; 7 typedef long long LL; 8 9 int T; 10 LL N; 11 12 int main() { 13 scanf("%d", &T); 14 for (int t = 1; t <= T; t++) { 15 LL ans = 0; 16 scanf("%lld", &N); 17 LL tmp = sqrt(N); 18 for (LL i = 2; i <= tmp; i++) { 19 ans += (N / i - i + 1) * i; 20 LL down = i + 1, up = N / i; 21 //if (down > up) continue; 因為down > up的情況只會出現于n可表示為n=x *x 的情況，此時down = up + 1。下方右式恰好為0 22 ans += (up + down) * (up - down + 1) / 2; 23 } 24 printf("Case %d: %lld\n", t, ans); 25 } 26 return 0; 27 }

?

轉載于:https://www.cnblogs.com/xFANx/p/7529281.html

總結

以上是生活随笔為你收集整理的LightOJ - 1098 A New Function的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。