编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#21410 #1072. zzy与飞行棋 Accepted 100 76 ms 4132 K C++ 17 / 849 B 自动化82-郭筠陶 2020-02-06 17:31:37
显示原始代码
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int max_ = 4e5 + 10;
vector<ull> phi(max_, 0);
vector<ull> primes;
void getPhi();
int main() {
    int n;
    cin >> n;
    getPhi();
    ull ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += phi.at(i);
    }
    cout << ans * 6;
    return 0;
}

void getPhi() {
    phi.at(1) = 1;
    for (int i = 2; i < max_; i++) {
        if (phi.at(i) == 0) {
            primes.push_back(i);
            phi.at(i) = i - 1;
        }
        for (int j = 0; j < primes.size() && primes.at(j) * i < max_; ++j) {
            int prime = primes.at(j);
            if (i % prime == 0) {
                phi.at(i * prime) = phi.at(i) * prime;
                break;
            } else {
                phi.at(i * prime) = phi.at(i) * (prime - 1);
            }
        }
    }
}
子任务 #1
Accepted
得分:100
测试点 #1
Accepted
得分:100
用时:7 ms
内存:4128 KiB

输入文件(1.in

192135

答案文件(1.out

67326849456

用户输出

67326849456

系统信息

Exited with return code 0
测试点 #2
Accepted
得分:100
用时:7 ms
内存:4092 KiB

输入文件(2.in

216798

答案文件(2.out

85720475280

用户输出

85720475280

系统信息

Exited with return code 0
测试点 #3
Accepted
得分:100
用时:7 ms
内存:4100 KiB

输入文件(3.in

1

答案文件(3.out

6

用户输出

6

系统信息

Exited with return code 0
测试点 #4
Accepted
得分:100
用时:7 ms
内存:4060 KiB

输入文件(4.in

359630

答案文件(4.out

235877186976

用户输出

235877186976

系统信息

Exited with return code 0
测试点 #5
Accepted
得分:100
用时:7 ms
内存:4132 KiB

输入文件(5.in

373264

答案文件(5.out

254100567060

用户输出

254100567060

系统信息

Exited with return code 0
测试点 #6
Accepted
得分:100
用时:7 ms
内存:4104 KiB

输入文件(6.in

208241

答案文件(6.out

79087626432

用户输出

79087626432

系统信息

Exited with return code 0
测试点 #7
Accepted
得分:100
用时:7 ms
内存:4116 KiB

输入文件(7.in

333144

答案文件(7.out

202412781024

用户输出

202412781024

系统信息

Exited with return code 0
测试点 #8
Accepted
得分:100
用时:7 ms
内存:4120 KiB

输入文件(8.in

333105

答案文件(8.out

202365467100

用户输出

202365467100

系统信息

Exited with return code 0
测试点 #9
Accepted
得分:100
用时:7 ms
内存:4060 KiB

输入文件(9.in

370945

答案文件(9.out

250953422700

用户输出

250953422700

系统信息

Exited with return code 0
测试点 #10
Accepted
得分:100
用时:6 ms
内存:4096 KiB

输入文件(10.in

334865

答案文件(10.out

204509727816

用户输出

204509727816

系统信息

Exited with return code 0
测试点 #11
Accepted
得分:100
用时:7 ms
内存:4064 KiB

输入文件(11.in

2

答案文件(11.out

12

用户输出

12

系统信息

Exited with return code 0