QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#354788 | #6566. Power of Divisors | kevinshan# | TL | 1ms | 3800kb | C++17 | 3.8kb | 2024-03-16 01:03:07 | 2024-03-16 01:03:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define f first
#define s second
#define trav(a,b) for(auto& a:b)
#define sz(a) a.size()
using ul = uint64_t;
using db = double;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define For(i,a) FOR(i,0,a)
ul modMul(ul a, ul b, const ul mod) {
ll ret = a*b-mod*(ul)((db)a*b/mod);
return ret+((ret<0)-(ret>=(ll)mod))*mod; }
ul modPow(ul a, ul b, const ul mod) {
if (b == 0) return 1;
ul res = modPow(a,b/2,mod); res = modMul(res,res,mod);
return b&1 ? modMul(res,a,mod) : res;
}
bool prime(ul n) { // not ll!
if (n < 2 || n % 6 % 4 != 1) return n-2 < 2;
ul A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022},
s = __builtin_ctzll(n-1), d = n>>s;
trav(a,A) { // ^ count trailing zeroes
ul p = modPow(a,d,n), i = s;
while (p != 1 && p != n-1 && a%n && i--) p = modMul(p,p,n);
if (p != n-1 && i != s) return 0;
}
return 1;
}
ul pollard(ul n) { // return some nontrivial factor of n
auto f = [n](ul x) { return modMul(x, x, n) + 1; };
ul x = 0, y = 0, t = 30, prd = 2, i = 1, q;
while (t++ % 40 || gcd(prd, n) == 1) { /// speedup: don't take gcd every it
if (x == y) x = ++i, y = f(x);
if ((q = modMul(prd, max(x,y)-min(x,y), n))) prd = q;
x = f(x), y = f(f(y));
}
return gcd(prd, n);
}
void factor_rec(ul n, map<ul,int>& cnt) {
if (n == 1) return;
if (prime(n)) { ++cnt[n]; return; }
ul u = pollard(n);
factor_rec(u,cnt), factor_rec(n/u,cnt);
}
vector<pair<ul,int>> factor(ul n) {
map<ul,int> cnt; factor_rec(n,cnt);
return vector<pair<ul,int>>(all(cnt));
}
inline namespace factorBasic {
template<class T> vector<pair<T,int>> factor2(T x) {
vector<pair<T,int>> pri;
for (T i = 2; i*i <= x; ++i) if (x % i == 0) {
int t = 0;
while (x % i == 0) x /= i, t ++;
pri.pb({i,t});
}
if (x > 1) pri.pb({x,1});
return pri;
}
/* Note:
* number of operations needed s.t.
* phi(phi(...phi(n)...))=1
* is O(log n).
* Euler's theorem: a^{\phi(p)}\equiv 1 (mod p), gcd(a,p)=1
*/
ll phi(ll x) {
trav(a,factor2(x)) x -= x/a.f;
return x;
}
template<class T> void tour(vector<pair<T,int>>& v,
vector<T>& V, int ind, T cur) {
if (ind == sz(v)) V.pb(cur);
else {
T mul = 1;
For(i,v[ind].s+1) {
tour(v,V,ind+1,cur*mul);
mul *= v[ind].f;
}
}
}
template<class T> vector<T> getDivi(T x) {
auto v = factor2(x);
vector<T> V; tour(v,V,0,(T)1); sort(all(V));
return V;
}
}
const ll INF = 1e18;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
if (fopen("input.in", "r")) {
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
}
ul x; cin>>x;
vector<pair<ul,int>> y = factor(x);
// trav(a,y) {
// cout << a.f << ' ' << a.s << endl;
// }
if(!y.size()) {
cout << 1 << endl;
return 0;
}
assert(y.size());
int cur = y[0].s;
trav(a,y) {
cur = gcd(cur, a.s);
}
// cout << "CUR " << cur << endl;
vector<int> tmp = getDivi(cur);
trav(a,tmp) {
ll base = 1;
ll pw2 = 1;
// cout << "A " << a << endl;
trav(b, y) {
int pw = b.s/cur*a;
for(int i=0;i<pw;i++) {
base *= b.f;
if (base > INF) {
cout << -1 << endl;
return 0;
}
}
pw2 *= (1+pw);
}
ll ans = 1;
for (int i=0;i<pw2;i++) {
ans *= base;
if (ans > INF) {
cout << -1 << endl;
return 0;
}
}
if (ans==x) {
cout << base << endl;
return 0;
}
}
cout << -1 << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3564kb
input:
15625
output:
25
result:
ok single line: '25'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
64000000
output:
20
result:
ok single line: '20'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
65536
output:
-1
result:
ok single line: '-1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
1
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3800kb
input:
10
output:
-1
result:
ok single line: '-1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
100
output:
-1
result:
ok single line: '-1'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
10000
output:
10
result:
ok single line: '10'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3556kb
input:
1000000000000000000
output:
100
result:
ok single line: '100'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
10372926089038969
output:
218089
result:
ok single line: '218089'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3800kb
input:
10642944803293201
output:
10157
result:
ok single line: '10157'
Test #11:
score: -100
Time Limit Exceeded
input:
10646534823110209