QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#354788#6566. Power of Divisorskevinshan#TL 1ms3800kbC++173.8kb2024-03-16 01:03:072024-03-16 01:03:07

Judging History

你现在查看的是最新测评结果

  • [2024-03-16 01:03:07]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3800kb
  • [2024-03-16 01:03:07]
  • 提交

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

output:


result: