相关链接
题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14573&rd=16882
题目大意
给定$n(n \le 10^9)$,问有多少组不同的$a^b=c^d$成立
要求$1 \le a,b,c,d \le n$
解题报告
假设$a^b=c^d$,我们在枚举到$gcd(a,c)$的时候计算
如果$gcd(a,c)=a=c$的话,贡献显然是$n$
所以我们枚举$gcd$只需要枚举到$\sqrt{n}$
又因为次数非常小,所以我们可以暴力算有多少种指数满足要求
于是总的复杂度大概是$\sqrt{n}$的
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; } };
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
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
188304 678935Its wonderful as your other posts : D, appreciate it for putting up. 992497
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
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
809966 188065I like this site so considerably, saved to favorites . 113498
148534 20983Thanks so significantly for yet another post. I be able to get that kind of details information. friend, and exactly. 785167
613399 629524Dead written topic matter, Genuinely enjoyed reading via . 579578
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
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
491673 513913This post post created me feel. I will write something about this on my weblog. 90590
811188 150531They call it the self-censor, merely because youre too self-conscious of your writing, too judgmental. 605606
864783 32794Definitely value bookmarking for revisiting. I surprise how so much attempt you set to create this kind of fantastic informative site. 86724
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
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
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.