Submission #20538592

Source Code Expand

#include <bits/stdc++.h>
#define rep(i, N) for(int i = 0; i < (int)N; i++)
#define CREP(i, l, r) for(int i = l; i <= r; i++)
using namespace std;
typedef long long ll;
typedef tuple<int,int,int> T; 
typedef pair<int,int> P;
typedef vector<int> V;
typedef vector<int> Vll;
const int INF = 1000000000;      //10^9, 2*INF
const ll LLINF = (1LL << 16);   // > 10^18 ll  2*LLINF

int main() {
    ll n;
    cin >> n;

    int P_MAX = 1000005;


    ll res = n;
    vector<bool> ch(P_MAX, false); 
    for(ll i = 2; i*i <= n; i++){
        if(ch[i]) continue;
        //cout << i << endl;

        ll tmp = i*i;
        while(tmp <= n){
            res--;
            if(tmp < P_MAX) ch[tmp] = true;
            tmp *= i;
        }
    }

    cout << res;
}

Submission Info

Submission Time
Task C - Unexpressed
User samari06
Language C++ (GCC 9.2.1)
Score 300
Code Size 787 Byte
Status AC
Exec Time 8 ms
Memory 3752 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
AC × 2
AC × 61
Set Name Test Cases
Sample 01_sample.txt, 02_sample.txt
All 01_sample.txt, 02_sample.txt, 10000000000_hand.txt, 10077695_pow.txt, 106830803_exp.txt, 1149_exp.txt, 1162261467_pow.txt, 125_hand.txt, 126_pow.txt, 129_pow.txt, 1341805554_exp.txt, 1468_exp.txt, 14_exp.txt, 15626_pow.txt, 167508771_exp.txt, 1697162_exp.txt, 177_exp.txt, 1920_exp.txt, 1977326742_pow.txt, 1997691865_exp.txt, 1_hand.txt, 2121516983_exp.txt, 21378622_exp.txt, 216_pow.txt, 233694_exp.txt, 2380105_exp.txt, 244140625_pow.txt, 2487595879_exp.txt, 2628894325_large.txt, 280262884_exp.txt, 3125_pow.txt, 31_exp.txt, 38114099_exp.txt, 4137_exp.txt, 41952318_exp.txt, 4971407775_large.txt, 49_pow.txt, 4_exp.txt, 50157498_exp.txt, 512_pow.txt, 5202647942_large.txt, 531441_pow.txt, 53_exp.txt, 5645468307_large.txt, 5669240390_large.txt, 609062_exp.txt, 6983776800_hand.txt, 728_pow.txt, 72977005_exp.txt, 729_pow.txt, 78126_pow.txt, 8002087506_large.txt, 8192_pow.txt, 84_exp.txt, 8731963982_large.txt, 909_exp.txt, 917490542_exp.txt, 919385315_exp.txt, 939887597_large.txt, 971207868_large.txt, 9_exp.txt
Case Name Status Exec Time Memory
01_sample.txt AC 8 ms 3532 KiB
02_sample.txt AC 2 ms 3620 KiB
10000000000_hand.txt AC 2 ms 3640 KiB
10077695_pow.txt AC 2 ms 3612 KiB
106830803_exp.txt AC 3 ms 3672 KiB
1149_exp.txt AC 2 ms 3544 KiB
1162261467_pow.txt AC 2 ms 3616 KiB
125_hand.txt AC 2 ms 3712 KiB
126_pow.txt AC 3 ms 3644 KiB
129_pow.txt AC 4 ms 3644 KiB
1341805554_exp.txt AC 3 ms 3560 KiB
1468_exp.txt AC 3 ms 3612 KiB
14_exp.txt AC 2 ms 3620 KiB
15626_pow.txt AC 3 ms 3536 KiB
167508771_exp.txt AC 3 ms 3540 KiB
1697162_exp.txt AC 3 ms 3592 KiB
177_exp.txt AC 2 ms 3696 KiB
1920_exp.txt AC 3 ms 3616 KiB
1977326742_pow.txt AC 3 ms 3684 KiB
1997691865_exp.txt AC 2 ms 3532 KiB
1_hand.txt AC 2 ms 3532 KiB
2121516983_exp.txt AC 2 ms 3748 KiB
21378622_exp.txt AC 2 ms 3668 KiB
216_pow.txt AC 2 ms 3672 KiB
233694_exp.txt AC 2 ms 3616 KiB
2380105_exp.txt AC 4 ms 3616 KiB
244140625_pow.txt AC 4 ms 3616 KiB
2487595879_exp.txt AC 3 ms 3616 KiB
2628894325_large.txt AC 2 ms 3616 KiB
280262884_exp.txt AC 3 ms 3616 KiB
3125_pow.txt AC 3 ms 3536 KiB
31_exp.txt AC 2 ms 3748 KiB
38114099_exp.txt AC 4 ms 3684 KiB
4137_exp.txt AC 2 ms 3716 KiB
41952318_exp.txt AC 3 ms 3616 KiB
4971407775_large.txt AC 2 ms 3696 KiB
49_pow.txt AC 3 ms 3616 KiB
4_exp.txt AC 3 ms 3748 KiB
50157498_exp.txt AC 2 ms 3612 KiB
512_pow.txt AC 4 ms 3616 KiB
5202647942_large.txt AC 3 ms 3696 KiB
531441_pow.txt AC 3 ms 3616 KiB
53_exp.txt AC 1 ms 3612 KiB
5645468307_large.txt AC 4 ms 3668 KiB
5669240390_large.txt AC 3 ms 3616 KiB
609062_exp.txt AC 3 ms 3748 KiB
6983776800_hand.txt AC 3 ms 3592 KiB
728_pow.txt AC 3 ms 3748 KiB
72977005_exp.txt AC 2 ms 3616 KiB
729_pow.txt AC 3 ms 3644 KiB
78126_pow.txt AC 2 ms 3548 KiB
8002087506_large.txt AC 4 ms 3716 KiB
8192_pow.txt AC 2 ms 3616 KiB
84_exp.txt AC 2 ms 3620 KiB
8731963982_large.txt AC 4 ms 3540 KiB
909_exp.txt AC 2 ms 3644 KiB
917490542_exp.txt AC 3 ms 3748 KiB
919385315_exp.txt AC 2 ms 3752 KiB
939887597_large.txt AC 2 ms 3672 KiB
971207868_large.txt AC 3 ms 3536 KiB
9_exp.txt AC 4 ms 3696 KiB