QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#594503	#6566. Power of Divisors	llg	AC ✓	61ms	7636kb	C++14	2.1kb	2024-09-28 00:59:21	2024-09-28 00:59:22

Judging History

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

[2024-09-28 00:59:22]
评测

测评结果：AC
用时：61ms
内存：7636kb

查看

[2024-09-28 00:59:21]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define deb(x) cout << #x << "=" << x << endl
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define sortall(x) sort(all(x))
#define tr(it, a) for (auto it = a.begin(); it != a.end(); it++)
#define mod 1000000007
const int N = 1e6 + 5;
int lp[N];
void sieve(int n)
{
    lp[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        for (int j = i; j <= n; j += i)
        {
            if (lp[j] == 0)
            {
                lp[j] = i;
            }
        }
    }
}
int number_of_divisors(int n)
{
    int ans = 1;
    while (n > 1)
    {
        int p = lp[n];
        int cnt = 0;
        while (n % p == 0)
        {
            n /= p;
            cnt++;
        }
        ans *= (cnt + 1);
    }
    return ans;
}
bool isprime(int n)
{
    if (n == 1)
        return false;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            return false;
        }
    }
    return true;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    sieve(1e6 + 2);
    ll x;
    cin >> x;
    ll cur = (ll)sqrt(x);
    ll ans = 1e18;
    if (cur * cur == x && isprime(cur))
    {
        ans = min(ans, cur);
    }
    // cout << number_of_divisors(20) << endl;
    for (int i = 1; i <= 1e6; i++)
    {
        int y = number_of_divisors(i);

        ll power = 1;
        bool dude = true;
        if (y == 2)
        {
            continue;
        }
        else
        {
            for (int j = 0; j < y; j++)
            {
                if (power > 1e18 / i)
                {
                    dude = false;
                    break;
                }
                power *= i;
            }
        }
        if (dude && power == x)
        {
            ans = min(ans, (ll)i);
        }
    }
    if (ans == 1e18)
    {
        cout << -1 << endl;
        return 0;
    }
    cout << ans << endl;
    return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 59ms

memory: 7456kb

input:

output:

result:

ok single line: '25'

Test #2:

score: 0

Accepted

time: 60ms

memory: 7636kb

input:

64000000

output:

result:

ok single line: '20'

Test #3:

score: 0

Accepted

time: 59ms

memory: 7452kb

input:

output:

-1

result:

ok single line: '-1'

Test #4:

score: 0

Accepted

time: 55ms

memory: 7456kb

input:

output:

result:

ok single line: '1'

Test #5:

score: 0

Accepted

time: 61ms

memory: 7416kb

input:

output:

-1

result:

ok single line: '-1'

Test #6:

score: 0

Accepted

time: 55ms

memory: 7576kb

input:

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0

Accepted

time: 54ms

memory: 7572kb

input:

output:

result:

ok single line: '10'

Test #8:

score: 0

Accepted

time: 50ms

memory: 7456kb

input:

1000000000000000000

output:

result:

ok single line: '100'

Test #9:

score: 0

Accepted

time: 57ms

memory: 7528kb

input:

10372926089038969

output:

result:

ok single line: '218089'

Test #10:

score: 0

Accepted

time: 50ms

memory: 7512kb

input:

10642944803293201

output:

result:

ok single line: '10157'

Test #11:

score: 0

Accepted

time: 54ms

memory: 7524kb

input:

10646534823110209

output:

103182047

result:

ok single line: '103182047'

Test #12:

score: 0

Accepted

time: 57ms

memory: 7536kb

input:

1073741824

output:

result:

ok single line: '32'

Test #13:

score: 0

Accepted

time: 57ms

memory: 7536kb

input:

output:

result:

ok single line: '11'

Test #14:

score: 0

Accepted

time: 54ms

memory: 7592kb

input:

output:

result:

ok single line: '6'

Test #15:

score: 0

Accepted

time: 59ms

memory: 7540kb

input:

output:

-1

result:

ok single line: '-1'

Test #16:

score: 0

Accepted

time: 52ms

memory: 7600kb

input:

16277421889

output:

result:

ok single line: '127583'

Test #17:

score: 0

Accepted

time: 55ms

memory: 7448kb

input:

output:

result:

ok single line: '13'

Test #18:

score: 0

Accepted

time: 61ms

memory: 7592kb

input:

output:

-1

result:

ok single line: '-1'

Test #19:

score: 0

Accepted

time: 57ms

memory: 7516kb

input:

output:

-1

result:

ok single line: '-1'

Test #20:

score: 0

Accepted

time: 57ms

memory: 7524kb

input:

205891132094649

output:

result:

ok single line: '243'

Test #21:

score: 0

Accepted

time: 55ms

memory: 7576kb

input:

output:

result:

ok single line: '5'

Test #22:

score: 0

Accepted

time: 56ms

memory: 7516kb

input:

2626114239841

output:

result:

ok single line: '1273'

Test #23:

score: 0

Accepted

time: 55ms

memory: 7516kb

input:

26269395104446321

output:

result:

ok single line: '12731'

Test #24:

score: 0

Accepted

time: 59ms

memory: 7420kb

input:

output:

-1

result:

ok single line: '-1'

Test #25:

score: 0

Accepted

time: 54ms

memory: 7508kb

input:

3596345248055296

output:

result:

ok single line: '88'

Test #26:

score: 0

Accepted

time: 53ms

memory: 7472kb

input:

output:

-1

result:

ok single line: '-1'

Test #27:

score: 0

Accepted

time: 57ms

memory: 7456kb

input:

output:

result:

ok single line: '2'

Test #28:

score: 0

Accepted

time: 57ms

memory: 7452kb

input:

output:

result:

ok single line: '8'

Test #29:

score: 0

Accepted

time: 50ms

memory: 7540kb

input:

output:

result:

ok single line: '7'

Test #30:

score: 0

Accepted

time: 59ms

memory: 7472kb

input:

output:

-1

result:

ok single line: '-1'

Test #31:

score: 0

Accepted

time: 54ms

memory: 7592kb

input:

576460752303423488

output:

-1

result:

ok single line: '-1'

Test #32:

score: 0

Accepted

time: 57ms

memory: 7524kb

input:

581431415926321

output:

24112889

result:

ok single line: '24112889'

Test #33:

score: 0

Accepted

time: 58ms

memory: 7452kb

input:

output:

-1

result:

ok single line: '-1'

Test #34:

score: 0

Accepted

time: 53ms

memory: 7516kb

input:

output:

result:

ok single line: '4'

Test #35:

score: 0

Accepted

time: 57ms

memory: 7600kb

input:

656100000000

output:

result:

ok single line: '30'

Test #36:

score: 0

Accepted

time: 54ms

memory: 7572kb

input:

output:

-1

result:

ok single line: '-1'

Test #37:

score: 0

Accepted

time: 50ms

memory: 7572kb

input:

output:

result:

ok single line: '9'

Test #38:

score: 0

Accepted

time: 54ms

memory: 7512kb

input:

output:

-1

result:

ok single line: '-1'

Test #39:

score: 0

Accepted

time: 59ms

memory: 7512kb

input:

output:

-1

result:

ok single line: '-1'

Test #40:

score: 0

Accepted

time: 54ms

memory: 7604kb

input:

8527674378686464

output:

result:

ok single line: '452'

Test #41:

score: 0

Accepted

time: 54ms

memory: 7532kb

input:

output:

result:

ok single line: '3'

Test #42:

score: 0

Accepted

time: 57ms

memory: 7472kb

input:

982134461213542729

output:

result:

ok single line: '994009'

Test #43:

score: 0

Accepted

time: 53ms

memory: 7540kb

input:

9992002399680016

output:

result:

ok single line: '9998'

Test #44:

score: 0

Accepted

time: 54ms

memory: 7528kb

input:

999269311525198921

output:

-1

result:

ok single line: '-1'

Test #45:

score: 0

Accepted

time: 58ms

memory: 7544kb

input:

999949000866995087

output:

-1

result:

ok single line: '-1'

Test #46:

score: 0

Accepted

time: 58ms

memory: 7516kb

input:

999995482005103081

output:

-1

result:

ok single line: '-1'

Test #47:

score: 0

Accepted

time: 53ms

memory: 7472kb

input:

999999969999997921

output:

-1

result:

ok single line: '-1'

Test #48:

score: 0

Accepted

time: 50ms

memory: 7544kb

input:

999999999999999989

output:

-1

result:

ok single line: '-1'

Test #49:

score: 0

Accepted

time: 59ms

memory: 7512kb

input:

999999999999999999

output:

-1

result:

ok single line: '-1'