[已解决]【C++板块提升计划】梦想护卫舰 第14期 取余

tommyyu

decimal行不行

1. import decimal
   
2. a, b = map(int, input().split())
   
3. print(int(decimal.Decimal(a) % decimal.Decimal(b)))

复制代码

zhangjinxuan

tommyyu 发表于 2023-1-26 20:45
decimal行不行

一帮老六

dolly_yos2

现在能看到（一部分）之前经历了长时间审核的回复了

zhangjinxuan

人造人 发表于 2023-1-26 12:17
你有什么话要说吗？
^_^

有！
你们这帮老六

1. [Error] boost/multiprecision/cpp_int.hpp: No such file or directory

复制代码

我才那个老六吧

zhangjinxuan

sfqxx 发表于 2023-1-26 19:29
自己选？？？？

呵呵

zhangjinxuan

元豪 发表于 2023-1-26 19:20
啊这......

（感觉我是不是有点过分了

zhangjinxuan

dolly_yos2 发表于 2023-1-26 15:31
应该是不需要高精度的
版本一（任意输入方式）：
版本二（需要将输入重定向到文件）：

不错不错，我很满意

（测试的时候我顺便写了个数据生成器上去，结果超时了，排查一下发现是数据生成器超时了，哈哈哈）

zhangjinxuan

dolly_yos2 发表于 2023-1-26 19:37
第21行是不是也有一点问题？

明天再评分吧，今天用完了

人造人

zhangjinxuan 发表于 2023-1-26 21:46
有！
你们这帮老六

^_^

zhangjinxuan

tommyyu 发表于 2023-1-26 20:45
decimal行不行

太大 decimal 就崩了（是不是我操作错了，我没用过

1. decimal.InvalidOperation: [<class 'decimal.DivisionImpossible'>]

复制代码

输入数据：

1. 7565521721998976389927665831246144538921968281367235378722916219634739798727419319539391588679818592277666374722947419138792565464137328872349233178547958481656738439975357856148634247733446987756315879633952797512872145816425352818178249817618781439875717698133717912462318749761975695197526421242444711682118786267513331389328134665148473613491636727372866995863146431871535827823456288992432978864725938444874878677169753171511496329225657884249393715984636369864646899989965376515865792623613682958673541987281228861322936131615789374839753239945848124959465276383638912345255821822173695668862137631714722212386872391833643812779935843986553388133312455182377829843822421655897183957681387187486693176878979516984985271441188192655461994761434483469848167914647387631398168272618139754257894646498585977842364261194959477788649569954295633459972517429867384168541294112118359268455273499999455767741989459846291678329649697848841314917576391132422724454573757562782668489386363411845549146215341 3158

复制代码

人造人

zhangjinxuan 发表于 2023-1-26 22:02
太大 decimal 就崩了（是不是我操作错了，我没用过

输入数据：

?
正确答案是多少？
这是什么意思？

1. sh-5.1$ time ./main <<EOF
   
2. > 7565521721998976389927665831246144538921968281367235378722916219634739798727419319539391588679818592277666374722947419138792565464137328872349233178547958481656738439975357856148634247733446987756315879633952797512872145816425352818178249817618781439875717698133717912462318749761975695197526421242444711682118786267513331389328134665148473613491636727372866995863146431871535827823456288992432978864725938444874878677169753171511496329225657884249393715984636369864646899989965376515865792623613682958673541987281228861322936131615789374839753239945848124959465276383638912345255821822173695668862137631714722212386872391833643812779935843986553388133312455182377829843822421655897183957681387187486693176878979516984985271441188192655461994761434483469848167914647387631398168272618139754257894646498585977842364261194959477788649569954295633459972517429867384168541294112118359268455273499999455767741989459846291678329649697848841314917576391132422724454573757562782668489386363411845549146215341 3158
   
3. > EOF
   
4. 1247
   
5. 
   
6. real        0m0.064s
   
7. user        0m0.021s
   
8. sys        0m0.013s
   
9. sh-5.1$
   

复制代码

这对吗？这不对吧？0.064秒你敢信？
这个规模的数字0.064秒？

zhangjinxuan

人造人 发表于 2023-1-26 22:10
?
正确答案是多少？
这是什么意思？

w h a t
我这使用数据生成器瞎搞出来的

zhangjinxuan

人造人 发表于 2023-1-26 22:10
?
正确答案是多少？
这是什么意思？

正确答案真是1247
(优美的话语)
估计这个库也使用了像我这样类似的算法？

人造人

zhangjinxuan 发表于 2023-1-26 22:16
w h a t
我这使用数据生成器瞎搞出来的

你有没有夸张点的数字（像上面那样的），并且是知道答案的
我想试试这个程序能不能给出正确答案，^_^

dolly_yos2

zhangjinxuan 发表于 2023-1-26 22:17
正确答案真是1247
(优美的话语)
估计这个库也使用了像我这样类似的算法？

很可能是因为数据不够大，毕竟只有 A 只有1000位
下面的测试里 A 恰好有 1e7 位，而 B 是 1999999999

1. $ cat test.cpp                                
   
2. #include <iostream>
   
3. #include <boost/multiprecision/cpp_int.hpp>
   
4. 
   
5. using boost::multiprecision::cpp_int;
   
6. 
   
7. int main() {
   
8.     cpp_int a, b;
   
9.     std::cin >> a >> b;
   
10.     std::cout << a % b << std::endl;
    
11.     return 0;
    
12. }%                                                                                                                                                                                                                                                                          
    
13. $ clang++ test.cpp
    
14. $ /usr/bin/time -p timeout -v 0.5s ./a.out < input
    
15. timeout: sending signal TERM to command ‘./a.out’
    
16. real 0.50
    
17. user 0.49
    
18. sys 0.00
    
19. $ cat test2.cpp                              
    
20. #include <iostream>
    
21. #include <string>
    
22. int main(){
    
23.     std::string a;
    
24.     uint64_t b;
    
25.     uint64_t result = 0;
    
26.     std::cin >> a >> b;
    
27.     for(const auto c: a){
    
28.         result = ((result << 3) + (result << 1) + (c - '0')) % b;
    
29.     }
    
30.     std::cout << result;
    
31.     return 0;
    
32. }%                                                                                                                                                                                                                                                                          
    
33. $ clang++ test2.cpp                              
    
34. $ /usr/bin/time -p timeout -v 0.5s ./a.out < input
    
35. 1313860644
    
36. real 0.13
    
37. user 0.13
    
38. sys 0.00
    
39. $ cat test3.cpp                                   
    
40. #include <cstdio>
    
41. #include <cstring>
    
42. 
    
43. char a[10000005];
    
44. int n, p;
    
45. 
    
46. long long eval_ans() {
    
47.         long long x = 1, avalue = 0;
    
48.         for (int i = n; i >= 1; --i) {
    
49.                 long long ap = (long long)(a[i] - '0') * x;
    
50.                 ap %= p;
    
51.                 avalue += ap;
    
52.                 avalue %= p;
    
53.                 x *= 10;
    
54.                 x %= p;
    
55.         }
    
56.         return avalue;
    
57. }
    
58. 
    
59. int main() {
    
60.         scanf("%s%d", a + 1, &p);
    
61.         n = strlen(a + 1);
    
62.         printf("%lld", eval_ans());
    
63. }
    
64. $ clang++ test3.cpp                              
    
65. $ /usr/bin/time -p timeout -v 0.5s ./a.out < input
    
66. 1313860644
    
67. real 0.07
    
68. user 0.07
    
69. sys 0.00
    
70. $ cat test.c
    
71. #include <unistd.h>
    
72. #include <sys/stat.h>
    
73. #include <sys/types.h>
    
74. int main(){
    
75.     enum{ BufferSize = 1024 };
    
76.     struct stat status;
    
77.     unsigned char buffer[BufferSize];
    
78.     ssize_t effective_length;
    
79.     if(fstat(STDIN_FILENO, &status) == -1){
    
80.         return 1;
    
81.     }
    
82.     off_t seek_offset = status.st_size > 11 ? -11 : -status.st_size;
    
83.     if(lseek(STDIN_FILENO, seek_offset, SEEK_END) == -1){
    
84.         return 1;
    
85.     }
    
86.     effective_length = read(STDIN_FILENO, buffer, BufferSize);
    
87.     unsigned long b = 0;
    
88.     ssize_t i = 0;
    
89.     while(buffer[i++] != ' ');
    
90.     while(i < effective_length && buffer[i] >= '0' && buffer[i] <= '9'){
    
91.         b = (b << 3) + (b << 1) + (buffer[i++] - '0');
    
92.     }
    
93.     lseek(STDIN_FILENO, 0, SEEK_SET);
    
94.     unsigned long result = 0;
    
95.     effective_length = i = 0;
    
96.     while(1){
    
97.         effective_length = read(STDIN_FILENO, buffer, BufferSize);
    
98.         for(i = 0; i < effective_length; i++){
    
99.             if(buffer[i] == ' ') goto end;
    
100.             result = ((result << 3) + (result << 1) + (buffer[i] - '0')) % b;
     
101.         }
     
102.     }
     
103.     end:
     
104.     i = 12;
     
105.     effective_length = 0;
     
106.     if(result == 0){
     
107.         effective_length = 1;
     
108.         buffer[i--] = '0';
     
109.     }
     
110.     while(result){
     
111.         effective_length++;
     
112.         buffer[i--] = (result % 10) + '0';
     
113.         result /= 10;
     
114.     }
     
115.     write(STDOUT_FILENO, buffer + i + 1, effective_length);
     
116.     return 0;
     
117. }%                                                                                                                                                                                                                                                                          
     
118. $ clang test.c
     
119. $ /usr/bin/time -p timeout -v 0.5s ./a.out < input
     
120. 1313860644
     
121. real 0.03
     
122. user 0.02
     
123. sys 0.00

复制代码