【TopCoder SRM713】PowerEquation

相关链接

题目传送门: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;   
		}
};

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

Leave a Reply to Slager hengelo Cancel reply

Your email address will not be published. Required fields are marked *