CQUPT OJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#6152 #1022. 萨斯噶joker！（hard version） Accepted 100 2936 ms 159580 K C++ 17 / 1.1 K new_user_2 2023-10-14 17:05:22
显示原始代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 10100000, M = 10000000;
int p[N], pr[N / 5], n, tot;
int phi[N];
ll sphi[N];

int main() {
    p[1] = 1;
    phi[1] = 1;
    for (int i = 2; i <= M; i++) {
        if (!p[i])
            p[i] = i, phi[i] = i - 1, pr[++tot] = i;
        for (int j = 1; j <= tot && pr[j] * i <= M; j++) {
            p[i * pr[j]] = pr[j];
            if (p[i] == pr[j]) {
                phi[i * pr[j]] = phi[i] * pr[j];
                break;
            } else {
                phi[i * pr[j]] = phi[i] * (pr[j] - 1);
            }
        }
    }
    for (int i = 1; i <= M; i++) sphi[i] = sphi[i - 1] + phi[i];
    int T;
    scanf("%d", &T);
    for (int tc = 0; tc < T; tc++) {
        int n, m;
        scanf("%d%d", &n, &m);
        if (n > m)
            swap(n, m);
        ll ans = 0;
        for (int l = 1; l <= n; l++) {
            int r = min(n / (n / l), m / (m / l));
            // l ... r
            ans += (sphi[r] - sphi[l - 1]) * (n / l) * (m / l);
            l = r;
        }
        printf("%lld\n", ans);
    }
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：943 ms
内存：159508 KiB

输入文件（1.in） 

10
4793 17979
18775 12424
3350 22010
24788 19497
28976 27892
6474 21718
16956 13533
7091 753
<28 bytes omitted>

答案文件（1.out） 

476040149
1399317850
393563805
3019169824
5222459184
801329783
1382484280
300791412
31093256
<13 bytes omitted>

用户输出 

476040149
1399317850
393563805
3019169824
5222459184
801329783
1382484280
300791412
3109325697
351331310

系统信息 

Exited with return code 0
测试点 #2
Accepted
得分：100
用时：649 ms
内存：159580 KiB

输入文件（2.in） 

3
100 200
1000 2000
1000000 2000000

答案文件（2.out） 

63542
9067212
17457854316166

用户输出 

63542
9067212
17457854316166

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：722 ms
内存：159488 KiB

输入文件（3.in） 

1000
5380 19380
23062 18444
24966 7925
27973 16875
19175 2584
12619 29646
4257 9984
3984 154
<12198 bytes omitted>

答案文件（3.out） 

583180624
2642316326
1151873118
2926621259
256907348
2271774411
230106374
333221190
22641412
<11308 bytes omitted>

用户输出 

583180624
2642316326
1151873118
2926621259
256907348
2271774411
230106374
333221190
226414123
803401576
590861808
1684310052
625
<10280 bytes omitted>

系统信息 

Exited with return code 0
测试点 #4
Accepted
得分：100
用时：622 ms
内存：159524 KiB

输入文件（4.in） 

1000
107366 100811
105502 101643
104771 103313
119799 106564
131214 100111
120996 123659
1298
<14906 bytes omitted>

答案文件（4.out） 

78372066863
77723395859
78592146275
92848415928
95171576327
110056982216
104528104631
9927617
<13339 bytes omitted>

用户输出 

78372066863
77723395859
78592146275
92848415928
95171576327
110056982216
104528104631
99276171544
110166776045
85895363673
97609
<12311 bytes omitted>

系统信息 

Exited with return code 0
CQUPT OJ Powered by SYZOJ.