编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#20478 #1072. zzy与飞行棋 Accepted 100 82 ms 2184 K C++ 17 / 1.4 K q3540555 2019-07-22 15:28:46
显示原始代码
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define spause() system("pause")

using namespace std;
typedef long long llong;
typedef unsigned long long ullong;
typedef pair<int, int> prdd;
typedef map<int, int> mpdd;

const int dinf = 0x7fffffff;
const llong llinf = 0x7fffffffffffffff;
const int p = 998244353;
llong starttime;

int phi[525000];
vector<int> ps;

int n;
llong ans = 0;

void Euler(int rge) {
    phi[1] = 1;
    for (int i = 2; i <= rge; i++) {
        if (phi[i] == 0) {
            phi[i] = i - 1;
            ps.push_back(i);
        }
        for (int j = 0; j < ps.size() && ps.at(j) <= rge / i; j++) {
            if (i % ps.at(j) == 0) {
                phi[i * ps.at(j)] = phi[i] * ps.at(j);
                break;
            } else
                phi[i * ps.at(j)] = phi[i] * (ps.at(j) - 1);
        }
    }
}
// I.	phi(p) = p - 1.
// II.	if : i mod p = 0 -> phi(i * p) = phi(i) * p.
// III. if : i mod p �� 0 -> phi(i * p) = phi(i) * (p-1).

inline llong ngmod(llong a, llong p) { return ((a % p) + p) % p; }

int main() {
    scanf("%d", &n);
    Euler(n);
    for (int i = 1; i <= n; i++) ans += phi[i];
    ans *= 6;
    printf("%lld", ans);

    spause();
    return 0;
}
子任务 #1
Accepted
得分:100
测试点 #1
Accepted
得分:100
用时:7 ms
内存:1312 KiB

输入文件(1.in

192135

答案文件(1.out

67326849456

用户输出

67326849456

系统信息

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

输入文件(2.in

216798

答案文件(2.out

85720475280

用户输出

85720475280

系统信息

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

输入文件(3.in

1

答案文件(3.out

6

用户输出

6

系统信息

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

输入文件(4.in

359630

答案文件(4.out

235877186976

用户输出

235877186976

系统信息

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

输入文件(5.in

373264

答案文件(5.out

254100567060

用户输出

254100567060

系统信息

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

输入文件(6.in

208241

答案文件(6.out

79087626432

用户输出

79087626432

系统信息

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

输入文件(7.in

333144

答案文件(7.out

202412781024

用户输出

202412781024

系统信息

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

输入文件(8.in

333105

答案文件(8.out

202365467100

用户输出

202365467100

系统信息

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

输入文件(9.in

370945

答案文件(9.out

250953422700

用户输出

250953422700

系统信息

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

输入文件(10.in

334865

答案文件(10.out

204509727816

用户输出

204509727816

系统信息

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

输入文件(11.in

2

答案文件(11.out

12

用户输出

12

系统信息

Exited with return code 0