【TopCoder SRM713】PowerEquation




给定$n(n \le 10^9)$,问有多少组不同的$a^b=c^d$成立
要求$1 \le a,b,c,d \le n$




#define LL long long
using namespace std;

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

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

class PowerEquation {
    	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;
				} 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;
   		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. 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

  3. 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

  4. 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

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

  6. 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


电子邮件地址不会被公开。 必填项已用*标注