Submission #32255878

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N;
    cin >> N;
    int sqrt_N(sqrt(N));

    // 線形篩で前計算 Θ(√N)時間
    vector<int> primes, least_prime_factor(sqrt_N + 1);
    for(int i = 2; i <= sqrt_N; ++i){
        if(!least_prime_factor[i]){
            primes.emplace_back(i);
            least_prime_factor[i] = i;
        }
        for(const auto p : primes){
            if(p * i > sqrt_N || p > least_prime_factor[i])break;
            least_prime_factor[p * i] = p;
        }
    }

    // φ(2), φ(3), ..., φ(Floor(√N)) を線形篩を用いて計算 Θ(√N)時間
    vector<int> totient(sqrt_N + 1);
    for(int i = 2; i <= sqrt_N; ++i){
        const auto p = least_prime_factor[i];
        totient[i] = i == p ? i - 1
                   : least_prime_factor[i / p] == p ? p * totient[i / p]
                   : (p - 1) * totient[i / p];
    }

    // 答えは 2 * ∑ Floor(N/i²) φ(i) + N
    int ans = 0;
    for(int i = 2; i <= sqrt_N; ++i)ans += N / i / i * totient[i];
    cout << 2 * ans + N << endl;

    return 0;
}

Submission Info

Submission Time
Task D - Together Square
User MMNMM
Language C++ (GCC 9.2.1)
Score 400
Code Size 1084 Byte
Status AC
Exec Time 7 ms
Memory 3688 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 2
AC × 14
Set Name Test Cases
Sample example_00.txt, example_01.txt
All example_00.txt, example_01.txt, test_00.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt
Case Name Status Exec Time Memory
example_00.txt AC 6 ms 3688 KiB
example_01.txt AC 2 ms 3480 KiB
test_00.txt AC 1 ms 3564 KiB
test_01.txt AC 2 ms 3452 KiB
test_02.txt AC 2 ms 3524 KiB
test_03.txt AC 2 ms 3584 KiB
test_04.txt AC 2 ms 3464 KiB
test_05.txt AC 2 ms 3468 KiB
test_06.txt AC 2 ms 3600 KiB
test_07.txt AC 2 ms 3484 KiB
test_08.txt AC 3 ms 3396 KiB
test_09.txt AC 7 ms 3556 KiB
test_10.txt AC 2 ms 3392 KiB
test_11.txt AC 2 ms 3688 KiB