QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#410599#6566. Power of DivisorsDanielChang#WA 1ms4068kbC++141.1kb2024-05-14 10:18:362024-05-14 10:18:37

Judging History

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

  • [2024-05-14 10:18:37]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4068kb
  • [2024-05-14 10:18:36]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define endl '\n'

/*
	Factoring Integers
	Factor any integer such that N * N > n
*/

const int N = 1e5+7;
vector<bool> is_prime;
vector<ll> primes;

void init_factor(){
	is_prime.assign(N+1, true);
	primes.clear();
	is_prime[0] = is_prime[1] = false;
	for(int i=2; i*i<=N; i++)
		for(int j=i*i; is_prime[i] && j<=N; j+=i)
			is_prime[j] = false;
	for(int i=2; i<=N; i++)
		if(is_prime[i]) primes.push_back(i);
}

// factor(420) = [[2,2], [3,1], [5,1], [7,1]]
// factor(74) = [[2,1], [37,1]]
int factor(ll n){
	assert(1LL*N*N > n);
	int v = 0;
	for(int i=1; i*i<=n; i++){
		if(n%i == 0){
		    v++;
		    if(i*i != n) v++;
		}
	}
	return v;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	init_factor();
	ll x;
	cin >> x;
	if(x==1){
	    cout << 1;
	    return 0;
	}
	for(ll p=2; p<=8; p++){
	    ll a = (ll) (pow((ld)x, 1.0 / (ld)p) + 0.0000001);
	    // cout << a << "^" << p << endl;
	    if((ll)pow(a, p) == x && factor(a) == p){
	        cout << a;
	        return 0;
	    }
	}
	cout << -1;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3928kb

input:

15625

output:

25

result:

ok single line: '25'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3972kb

input:

64000000

output:

20

result:

ok single line: '20'

Test #3:

score: 0
Accepted
time: 0ms
memory: 4016kb

input:

65536

output:

-1

result:

ok single line: '-1'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3752kb

input:

1

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 0ms
memory: 4068kb

input:

10

output:

-1

result:

ok single line: '-1'

Test #6:

score: 0
Accepted
time: 1ms
memory: 4064kb

input:

100

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0
Accepted
time: 1ms
memory: 4068kb

input:

10000

output:

10

result:

ok single line: '10'

Test #8:

score: -100
Wrong Answer
time: 1ms
memory: 3916kb

input:

1000000000000000000

output:

-1

result:

wrong answer 1st lines differ - expected: '100', found: '-1'