# 【TopCoder SRM713】PowerEquation

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1000000007;
const int N = 100000;

int gcd[100][100];
bool vis[N];

class PowerEquation {
public:
int count(int n) {
memset(vis, 0, sizeof(vis));
for (int i=1;i<=50;i++) {
for (int j=1;j<=50;j++) {
gcd[i][j] = GCD(i, j);
}
}

int ret = (LL)n * n % MOD, dec = 0;
for (int i=2;1;i++) {
if (i * i > n) {
ret = (ret + (n - i + 1ll - dec) * n) % MOD;
break;
} else {
if (vis[i]) continue;
for (LL j=i*i;j<=n;j*=i) {
if (j * j <= n) vis[j] = 1;
else ++dec;
}

int mx = 1, tmp = 0; LL cur = i;
while (cur * i <= n) cur *= i, ++mx;
for (int a=1;a<=mx;a++) {
for (int b=1;b<=mx;b++) {
int c = max(b,a) / gcd[a][b];
tmp = (tmp + n / c) % MOD;
}
}
ret = (ret + tmp) % MOD;
}
}
return ret;
}
private:
int GCD(int a, int b) {
return b? GCD(b, a%b): a;
}
};


## 16 thoughts to “【TopCoder SRM713】PowerEquation”

1. 176269 638339Oh my goodness! an amazing article dude. Thanks a ton Nonetheless I will probably be experiencing difficulty with ur rss . Do not know why Not able to join it. Can there be every person acquiring identical rss problem? Anybody who knows kindly respond. Thnkx 807280

2. 704708 926427hello I was extremely impressed with the setup you used with this website. I use blogs my self so great job. definatly adding to bookmarks. 305112

3. 188304 678935Its wonderful as your other posts : D, appreciate it for putting up. 992497

4. 11151 469883This Los angeles Weight Loss diet happens to be an low and flexible going on a diet application meant for typically trying to drop the weight as well within the have a a lot healthier lifetime. shed weight 528709

5. 208014 104020An fascinating discussion is worth comment. I feel that you need to have to write a lot more on this matter, it might not be a taboo topic but generally individuals are not enough to speak on such topics. To the next. Cheers 321876

6. 809966 188065I like this site so considerably, saved to favorites . 113498

7. 148534 20983Thanks so significantly for yet another post. I be able to get that kind of details information. friend, and exactly. 785167

8. 613399 629524Dead written topic matter, Genuinely enjoyed reading via . 579578

9. 777630 927045Greetings! This really is my initial comment here so I just wanted to give a quick shout out and tell you I genuinely enjoy reading via your blog posts. Can you recommend any other blogs/websites/forums that deal with the same topics? Thank you so much! 377105

10. 360203 464402You produced some decent points there. I looked on the web for that issue and discovered a lot of people is going together with with the internet site. 563771

11. 491673 513913This post post created me feel. I will write something about this on my weblog. 90590

12. 811188 150531They call it the self-censor, merely because youre too self-conscious of your writing, too judgmental. 605606

13. 864783 32794Definitely value bookmarking for revisiting. I surprise how so much attempt you set to create this kind of fantastic informative site. 86724

14. 257078 767965I just could not go away your web site before suggesting that I incredibly enjoyed the usual info a person supply to your guests? Is going to be back ceaselessly so that you can inspect new posts. 450129

15. I truly appreciate this post. I’ve been looking all over for this! Thank goodness I found it on Bing. You’ve made my day! Thank you again

16. Very good written story. It will be valuable to anyone who usess it, including yours truly :). Keep up the good work – i will definitely read more posts.