Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- typedef long long LL;
- map<LL,LL> X2;
- LL F2(LL N){
- return N*(N-1)/2;
- }
- LL R2(LL N){
- if(N==1) return 0;
- if(X2[N]) return X2[N];
- LL sum = F2(N);
- LL m=2;
- while(true){
- LL x = N/m;
- LL nxt = N/x;
- if(nxt >= N) return X2[N] = sum - (N-m+1)*R2(N/m);
- sum -= (nxt-m+1) * R2(N/m);
- m = nxt+1;
- }
- }
- int main(){
- cout << R2(1000) + 1; // Sum[EulerTotient[i], i, 1, 1000]
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement