QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#86808	#5715. 幂次	james1BadCreeper	100 ✓	256ms	60312kb	C++14	1.2kb	2023-03-11 08:06:27	2023-03-11 08:06:28

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-03-11 08:06:28]
评测

测评结果：100
用时：256ms
内存：60312kb

查看

[2023-03-11 08:06:27]
提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 
const i64 N = 1e18; 

int tot; 
i64 num[30000005];

int calc(i64 n) {
    int idx = lower_bound(num + 1, num + tot + 1, n) - num;
    if (idx > tot || (idx <= tot && num[idx] > n)) --idx; 
    return idx + sqrtf64x(n); 
}

int main(void) {
    for (i64 i = 2; i <= 1000000; ++i) {
        i64 k = i * i; 
        for (; k <= N / i; ) {
            k *= i; i64 sq = sqrtf64x(k); 
            if (sq * sq != k) num[++tot] = k;
        }
    }
    sort(num + 1, num + tot + 1); 
    tot = unique(num + 1, num + tot + 1) - (num + 1);  
    i64 n; int k; cin >> n >> k; 
    if (k == 1) return printf("%lld\n", n), 0; 
    else if (k == 2) return cout << calc(n) << "\n", 0; 
    else {
        set<i64> s; s.insert(1); 
        for (i64 i = 2; i <= 1000000; ++i) {
            int op = 1, flag = 1; i64 res = 1;  
            while (op < k) {
                ++op; 
                if (res <= n / i) res *= i; 
                else { flag = 0; break; }
            }
            for (; res <= n / i; ) {
                res *= i; 
                s.insert(res); 
            }
        }
        cout << s.size() << "\n"; 
    }
    return 0;
}

Source code, Language: C++14

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5

Accepted

time: 94ms

memory: 11684kb

input:

92 1

output:

result:

ok 1 number(s): "92"

Test #2:

score: 5

Accepted

time: 94ms

memory: 11972kb

input:

96 2

output:

result:

ok 1 number(s): "12"

Test #3:

score: 5

Accepted

time: 102ms

memory: 11552kb

input:

9383 3

output:

result:

ok 1 number(s): "37"

Test #4:

score: 5

Accepted

time: 93ms

memory: 12180kb

input:

9830 2

output:

result:

ok 1 number(s): "124"

Test #5:

score: 5

Accepted

time: 99ms

memory: 11484kb

input:

927700 3

output:

result:

ok 1 number(s): "149"

Test #6:

score: 5

Accepted

time: 90ms

memory: 11716kb

input:

972504 2

output:

result:

ok 1 number(s): "1097"

Test #7:

score: 5

Accepted

time: 93ms

memory: 12628kb

input:

94345650 3

output:

result:

ok 1 number(s): "605"

Test #8:

score: 5

Accepted

time: 85ms

memory: 12244kb

input:

98811802 2

output:

result:

ok 1 number(s): "10429"

Test #9:

score: 5

Accepted

time: 99ms

memory: 13288kb

input:

9328450690 3

output:

result:

ok 1 number(s): "2541"

Test #10:

score: 5

Accepted

time: 90ms

memory: 12724kb

input:

9775065820 2

output:

result:

ok 1 number(s): "101083"

Test #11:

score: 5

Accepted

time: 97ms

memory: 13660kb

input:

948459050000 3

output:

result:

ok 1 number(s): "11116"

Test #12:

score: 5

Accepted

time: 84ms

memory: 12216kb

input:

993120563000 2

output:

result:

ok 1 number(s): "1006727"

Test #13:

score: 5

Accepted

time: 106ms

memory: 14764kb

input:

93781484300000 3

output:

result:

ok 1 number(s): "49275"

Test #14:

score: 5

Accepted

time: 89ms

memory: 12372kb

input:

98250912400000 2

output:

result:

ok 1 number(s): "9958807"

Test #15:

score: 5

Accepted

time: 120ms

memory: 21992kb

input:

9272034040000000 3

output:

result:

ok 1 number(s): "221661"

Test #16:

score: 5

Accepted

time: 91ms

memory: 11344kb

input:

9981231040000000 2

output:

100122721

result:

ok 1 number(s): "100122721"

Test #17:

score: 5

Accepted

time: 256ms

memory: 60312kb

input:

942817384000000000 3

output:

result:

ok 1 number(s): "1016053"

Test #18:

score: 5

Accepted

time: 81ms

memory: 12848kb

input:

987478897000000000 2

output:

994718860

result:

ok 1 number(s): "994718860"

Test #19:

score: 5

Accepted

time: 89ms

memory: 12684kb

input:

932205945000000000 2

output:

966488284

result:

ok 1 number(s): "966488284"

Test #20:

score: 5

Accepted

time: 94ms

memory: 12472kb

input:

992520149596833024 2

output:

997253882

result:

ok 1 number(s): "997253882"

Extra Test:

score: 0

Extra Test Passed