[已解决]python分数

zzzyf

分数
共 5 个测试点  每个测试点 20 分

每个测试点限时 3 秒  运行内存上限 512MB

查看本题最近一次测评结果

一个序列有 nn 个数，编号 1\dots n1…n ，最初第 ii 个数是 \frac 1 i
i
1
​       
（i\in[1,n]i∈[1,n]）。每次选取编号最小且分母不为 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
&#8203;       
  
3
1
&#8203;       
  
4
1
&#8203;       

第一次操作 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
&#8203;       
  
2
1
&#8203;       

第二次操作 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
&#8203;       

第三次操作 q=2q=2 ，执行 a=a\times q+ba=a×q+b 后 a=51a=51 ，序列变为：

12\quad 6\quad 4\quad 3
12643
此时所有数分母均为 11 ，过程结束。

最佳答案

月排行榜 / 总排行榜

永恒的蓝色梦想

2020-8-10 11:08:33

陈尚涵 发表于 2020-8-10 10:48
这个用Java写效率会更快

1. #define _CRT_SECURE_NO_WARNINGS
   
2. #include<stdio.h>
   
3. #include<stdint.h>
   
4. 
   
5. 
   
6. 
   
7. uint64_t gcd(uint64_t a, uint64_t b) {
   
8.     uint64_t c;
   
9. 
   
10.     while (b) {
    
11.         c = a % b;
    
12.         a = b;
    
13.         b = c;
    
14.     }
    
15. 
    
16.     return a;
    
17. }
    
18. 
    
19. 
    
20. 
    
21. int main() {
    
22.     uint32_t n, a, b, num, temp;
    
23.     uint64_t product = 1;
    
24. 
    
25.     scanf("%u%u%u", &n, &a, &b);
    
26. 
    
27. 
    
28.     for (num = 1; num <= n; num++) {
    
29.         if (product % num) {
    
30.             temp = num / gcd(num, product);
    
31.             product *= temp;
    
32.             a *= temp;
    
33.             a += b;
    
34.         }
    
35.     }
    
36. 
    
37. 
    
38.     printf("%u", a);
    
39.     return 0;
    
40. }

复制代码

跳转到最佳答案楼层

zltzlt

这是……？？

永恒的蓝色梦想

兄弟，我看你题目看得好苦

zzzyf

题目原题

zzzyf

谢谢

zzzyf

但是确实超时了

永恒的蓝色梦想

zzzyf 发表于 2020-8-9 17:17
但是确实超时了

麻烦回复啊不然我看不到

永恒的蓝色梦想

zzzyf 发表于 2020-8-9 17:17
但是确实超时了

我能用 C 语言写吗

zzzyf

能

永恒的蓝色梦想

zzzyf 发表于 2020-8-9 17:20
能

试试这个：

1. from math import gcd
   
2. 
   
3. n, a, b = map(int, input().split())
   
4. num = product = 1
   
5. 
   
6. 
   
7. while num <= n:
   
8.     if product % num:
   
9.         temp = num // gcd(num, product)
   
10.         product *= temp
    
11.         a = (a * temp + b) % 4294967296
    
12. 
    
13.     num += 1
    
14. 
    
15. 
    
16. print(a)

复制代码

陈尚涵

永恒的蓝色梦想 发表于 2020-8-9 20:03
试试这个：

这个用Java写效率会更快

永恒的蓝色梦想

陈尚涵 发表于 2020-8-10 10:48
这个用Java写效率会更快

用 C 更快。

永恒的蓝色梦想

陈尚涵 发表于 2020-8-10 10:48
这个用Java写效率会更快

1. #define _CRT_SECURE_NO_WARNINGS
   
2. #include<stdio.h>
   
3. #include<stdint.h>
   
4. 
   
5. 
   
6. 
   
7. uint64_t gcd(uint64_t a, uint64_t b) {
   
8.     uint64_t c;
   
9. 
   
10.     while (b) {
    
11.         c = a % b;
    
12.         a = b;
    
13.         b = c;
    
14.     }
    
15. 
    
16.     return a;
    
17. }
    
18. 
    
19. 
    
20. 
    
21. int main() {
    
22.     uint32_t n, a, b, num, temp;
    
23.     uint64_t product = 1;
    
24. 
    
25.     scanf("%u%u%u", &n, &a, &b);
    
26. 
    
27. 
    
28.     for (num = 1; num <= n; num++) {
    
29.         if (product % num) {
    
30.             temp = num / gcd(num, product);
    
31.             product *= temp;
    
32.             a *= temp;
    
33.             a += b;
    
34.         }
    
35.     }
    
36. 
    
37. 
    
38.     printf("%u", a);
    
39.     return 0;
    
40. }

复制代码

zzzyf

谢谢了