【TopCoder】[TCO2013 2A] The Powers

相关链接

题目传送门：https://arena.topcoder.com/#/u/practiceCode/15610/27970/12185/1/316868
数据生成器：http://paste.ubuntu.com/24089972/
官方题解：https://apps.topcoder.com/wiki/display/tc/TCO+2013+Round+2A
神犇题解：http://picks.logdown.com/posts/208980-solutions-to-topcoder-open-2013s-hard-problems

解题报告

我们想办法来统计重复出现的次数，然后用$A \cdot B$减掉这个数就是答案了
那么考虑$x^a=y^b$，我们直接枚举$x,y$肯定会算重，于是我们枚举$\gcd (x,y)$
这样的话，枚举的$\gcd$之间就不会互相影响了

假设当前枚举的$\gcd$为$d$，那么我们就是要统计$(d^i)^a=(d^j)^b$重复了多少
但直接统计比较麻烦，于是我们统计出现的不同个数有多少
于是问题转化为：$i \cdot a$有多少种不同的取值，其中$a \in [1,10^9]$，$i \in [1,\log_d 10^9]$

因为$i$的范围只有不到$30$于是我们就可以用打个表
但打表是不优雅的，于是我们搞一搞优化：

不妨设我们求$x^y \in [B(k-1),Bk]$时的解
不难发现，若$i,j \in [k,\log_d 10^9]$且$i$是$j$的倍数
那么$i$能凑出来的，$j$也能凑出来，于是我们就可以删去$i$
这时我们搞一搞发现：删掉之后剩余元素的个数不超过$15$
于是我们就可以愉快地容斥啦！

这样搞的话，时间复杂度是$O((\sqrt A + 2^{15}) \log^2A )$的
还是跑得挺快的

另外，这题的$A,B$可以出到$10^{18}$去
但是我不会QwQ
这里扔一份代码吧：http://paste.ubuntu.com/24089979/
哪位神犇如果看懂了，给我讲讲可好 _(:з」∠)_

Code

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

const int N = 32000;

int vis[N],pri[N],tot;
LL ans[40]; 
vector<int> que;

class ThePowers{
	public:
		long long find(LL A, LL B) {
			prework(N-1, B); LL ret = B - 1;
			for (LL r=2,t,vi;r*r<=A;r++) {
				if (judge(r)) { 
					for (t=0,vi=r;vi<=A;t++,vi*=r);
					ret += t * B - ans[t]; 
				}
			} 
			return (LL)A * B - ret;
		}
	private:
		LL DFS(LL t, LL B, LL cnt, LL lcm) {
			if (!t) {
				if (cnt & 1) return (LL)B / lcm;
				else if (cnt) return -(LL)B / lcm;
				else return 0; 
			} else {
				return 
				DFS(t-1, B, cnt, lcm) + 
				DFS(t-1, B, cnt+1, lcm / Gcd(lcm, que[t-1]) * que[t-1]);
			}
		}
		inline void prework(LL n, LL B) {
			for (int i=2;i<=n;i++) {
				if (!vis[i]) vis[i] = i, pri[++tot] = i;
				for (int j=1;j<=tot&&pri[j]*i<=n;j++) {
					vis[i*pri[j]] = pri[j];
					if (i % pri[j] == 0) break;
				}
			}
			for (int i=1;i<30;i++) {
				for (int j=1;j<=i;j++) {
					que.clear();
					for (int k=j,tag=0;k<=i;k++,tag=0) {
						for (int l=que.size()-1;l>=0;l--) 
							if (k % que[l] == 0) 
								{tag = 1; break;}
						if (!tag) que.push_back(k);
					}
					ans[i] += DFS(que.size(), j * B, 0, 1);
					ans[i] -= DFS(que.size(), j * B - B, 0, 1);
				}
					cout<<ans[i]<<endl;;
			}
		}
		inline LL Gcd(LL a, LL b) {
			return b? Gcd(b, a%b): a;	
		}
		inline bool judge(int w) {
			int GCD = 0;
			for (int t=0,p=vis[w];w>1;t=0,p=vis[w]) {
				while (w % p == 0) t++, w /= p;
				if (!GCD) GCD = t;
				else GCD = Gcd(GCD, t);
			}
			return GCD == 1;
		}
};

吐槽

今天两道数论题就坑了我一天
上午那个二次剩余的东西，简直没法调试
下午+晚上全™坑这题上面了，也是简直了