python分数
分数共 5 个测试点每个测试点 20 分
每个测试点限时 3 秒运行内存上限 512MB
查看本题最近一次测评结果
一个序列有 nn 个数，编号 1\dots n1…n ，最初第 ii 个数是 \frac 1 i
i
1
（i\ini∈）。每次选取编号最小且分母不为 11 的分数，设这个分数为 \frac p q
q
p
，令所有分数都乘上 qq 并化简，重复这个过程直到所有数分母均为 11 。
你需要按顺序求出每次操作乘上的数 qq 。
为了减少输出量，采用如下输出方式：给定两个整数 a,ba,b ，对于每次操作的 qq ，执行 a=a\times q+ba=a×q+b ，最后输出 aa 对 2^{32}2
32
取模的值。
输入格式
一行三个正整数 n, a, bn,a,b 。
输出格式
一行一个整数，表示答案。
数据范围与约定
对于 20\%20% 的数据，保证 n\leq 7n≤7 。
对于 40\%40% 的数据，保证 n\leq 5000n≤5000 。
对于 60\%60% 的数据，保证 n\leq 50000n≤50000 。
对于 100\%100% 的数据， 0< n\leq 8\times 10^70<n≤8×10
7
， 0< a,b< 2^{32}0<a,b<2
32
。
样例输入
4 2 3
样例输出
51
样例解释
初始 a=2,b=3a=2,b=3 ，序列为：
1\quad\frac 1 2\quad\frac 1 3\quad\frac 1 4
1
2
1
3
1
4
1
第一次操作 q=2q=2 ，执行 a=a\times q+ba=a×q+b 后 a=7a=7 ，序列变为：
2\quad 1\quad\frac 2 3\quad\frac 1 2
21
3
2
2
1
第二次操作 q=3q=3 ，执行 a=a\times q+ba=a×q+b 后 a=24a=24 ，序列变为：
6\quad 3\quad 2\quad\frac 3 2
632
2
3
第三次操作 q=2q=2 ，执行 a=a\times q+ba=a×q+b 后 a=51a=51 ，序列变为：
12\quad 6\quad 4\quad 3
12643
此时所有数分母均为 11 ，过程结束。 这是……？？ 兄弟，我看你题目看得好苦 题目原题 谢谢 但是确实超时了
zzzyf 发表于 2020-8-9 17:17
但是确实超时了
麻烦回复啊{:10_277:}不然我看不到 zzzyf 发表于 2020-8-9 17:17
但是确实超时了
我能用 C 语言写吗{:10_277:} 能 zzzyf 发表于 2020-8-9 17:20
能
试试这个：from math import gcd
n, a, b = map(int, input().split())
num = product = 1
while num <= n:
if product % num:
temp = num // gcd(num, product)
product *= temp
a = (a * temp + b) % 4294967296
num += 1
print(a) 永恒的蓝色梦想 发表于 2020-8-9 20:03
试试这个：
这个用Java写效率会更快 陈尚涵 发表于 2020-8-10 10:48
这个用Java写效率会更快
用 C 更快。 陈尚涵 发表于 2020-8-10 10:48
这个用Java写效率会更快
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdint.h>
uint64_t gcd(uint64_t a, uint64_t b) {
uint64_t c;
while (b) {
c = a % b;
a = b;
b = c;
}
return a;
}
int main() {
uint32_t n, a, b, num, temp;
uint64_t product = 1;
scanf("%u%u%u", &n, &a, &b);
for (num = 1; num <= n; num++) {
if (product % num) {
temp = num / gcd(num, product);
product *= temp;
a *= temp;
a += b;
}
}
printf("%u", a);
return 0;
} 谢谢了
页:
[1]