[已解决]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写效率会更快

#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;
}

跳转到最佳答案楼层

zltzlt

这是……？？

永恒的蓝色梦想

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

zzzyf

题目原题

zzzyf

谢谢

zzzyf

但是确实超时了

永恒的蓝色梦想

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

麻烦回复啊不然我看不到

永恒的蓝色梦想

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

我能用 C 语言写吗

zzzyf

能

永恒的蓝色梦想

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;
}

zzzyf

谢谢了