Advertisement
Guest User

Untitled

a guest
Aug 24th, 2013
1,216
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.49 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3. typedef long long LL;
  4. map<LL,LL> X2;
  5. LL F2(LL N){
  6.     return N*(N-1)/2;
  7. }
  8. LL R2(LL N){
  9.     if(N==1) return 0;
  10.     if(X2[N]) return X2[N];
  11.     LL sum = F2(N);
  12.     LL m=2;
  13.     while(true){
  14.         LL x = N/m;
  15.         LL nxt = N/x;
  16.         if(nxt >= N) return X2[N] = sum - (N-m+1)*R2(N/m);
  17.         sum -= (nxt-m+1) * R2(N/m);
  18.         m = nxt+1;
  19.     }
  20. }
  21. int main(){
  22.     cout << R2(1000) + 1;   // Sum[EulerTotient[i], i, 1, 1000]
  23.     return 0;
  24. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement