如何通过 loj hack
查看原帖
如何通过 loj hack
857323
linxuanrui楼主2024/5/18 18:48

RT,TLE on loj #1。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,cnt;
vector<int> ans;
int qpow(int a,int b){
	int ans = 1;
	while(b){
		if(b & 1)ans *= a;
		a *= a,b >>= 1;
	}
	return ans;
}
bool check(int x){
	for(int i = 2;i * i <= x;i++){
		if(x % i == 0)return false;
	}
	return x >= 2;
}
vector<pair<int,int> > get(int x,int minn){
	vector<pair<int,int> > t;
	for(int i = 1;(1ll << i + 1) - 1 <= x;i++){
		int l = 2,r = pow(x,1.0 / i) + 10;
		while(r - l > 1){
			int mid = (l + r) / 2;
			if((qpow(mid,i + 1) - 1) / (mid - 1) <= x)l = mid;
			else r = mid;
		}
		if(l < minn)break;
		if(check(l) && (qpow(l,i + 1) - 1) / (l - 1) == x)t.push_back({l,i});
	}
	return t;
}
void dfs(int now,int minn,int tmp){
//	for(int i = 1;i <= cnt;i++)cout << "-";
//	cout << now << " " << minn << " " << tmp << endl;
	if(now == 1){
		ans.push_back(tmp);
		return;
	}
	for(int i = 1;i * i <= now;i++)if(now % i == 0){
		if(i >= minn){
			vector<pair<int,int> > t = get(i,minn);
			for(auto j : t){
				cnt++;
				dfs(now / i,j.first + 1,tmp * qpow(j.first,j.second));
				cnt--;
			}
		}
		if(i * i != now && now / i >= minn){
			int ttt = now / i;
			vector<pair<int,int> > t = get(ttt,minn);
			for(auto j : t){
				cnt++;
				dfs(i,j.first + 1,tmp * qpow(j.first,j.second));
				cnt--;
			}
		}
	}
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//    freopen("a.txt","w",stdout);
//	auto t = get(511,1);
//	for(auto i : t)cout << i.first << " " << i.second << endl;return 0;
    while(cin >> n){
    	ans.clear();
    	dfs(n,1,1);
    	cout << ans.size() << endl;
    	sort(ans.begin(),ans.end());
    	for(auto i : ans)cout << i << " ";
    	if(ans.size())cout << endl;
	}
}
2024/5/18 18:48
加载中...