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

zhangjinxuan

上一关：细胞分裂

梦想护卫舰 第14期 高精度取余

告别 hanks 博士，梦想护卫舰 再次出发，这时，海面上出现了一头鲸鱼

原来，鲸鱼有一道题目不会，想了 1e9 + 7 天都没有想出来，而鲸鱼听说 聪明才智 的你们会经过这里，便想向你们请教

题目是这样的：

有两个数 A, B。A 是一个合法的正整数，请你求出 A % B 等于几？

输入格式

1. A B

复制代码

输出格式

1. 【A % B 的结果】

复制代码

输入样例

1. 888333 823

复制代码

输出样例

1. 316

复制代码

数据范围
以下记 n = A的长度
对于 100% 的数据，1 <= n <= 1e7，1 <= B <= 2e9
对于其中 60% 的数据，1 <= n <= 1000

时间限制：500ms （友情提示，C++评测机跑 1e7 只要 200ms）
空间限制：256mb

注意：本题个人原创，转载请注明出处

                               
登录/注册后可看大图

答案与解析

游客，如果您要查看本帖隐藏内容请回复

最佳战士
名字：dolly_yos2
奖励：最佳答案+5鱼币5荣誉

                               
登录/注册后可看大图

鲸鱼为了感谢你，给了你一张藏宝图……

To be continue……

下一关：画树

最佳答案

月排行榜 / 总排行榜

dolly_yos2

2023-1-26 15:31:39

应该是不需要高精度的
版本一（任意输入方式）：

1. #include <iostream>
   
2. #include <string>
   
3. int main(){
   
4.     std::string a;
   
5.     uint64_t b;
   
6.     uint64_t result = 0;
   
7.     std::cin >> a >> b;
   
8.     for(const auto c: a){
   
9.         result = ((result << 3) + (result << 1) + (c - '0')) % b;
   
10.     }
    
11.     std::cout << result;
    
12.     return 0;
    
13. }

复制代码

版本二（需要将输入重定向到文件）：

1. #include <unistd.h>
   
2. #include <sys/stat.h>
   
3. int main(){
   
4.     enum{ BufferSize = 1024 };
   
5.     struct stat status;
   
6.     unsigned char buffer[BufferSize];
   
7.     ssize_t effective_length;
   
8.     if(fstat(STDIN_FILENO, &status) == -1){
   
9.         return 1;
   
10.     }
    
11.     off_t seek_offset = status.st_size > 11 ? -11 : -status.st_size;
    
12.     if(lseek(STDIN_FILENO, seek_offset, SEEK_END) == -1){
    
13.         return 1;
    
14.     }
    
15.     effective_length = read(STDIN_FILENO, buffer, BufferSize);
    
16.     unsigned long b = 0;
    
17.     ssize_t i = 0;
    
18.     while(buffer[i++] != ' ');
    
19.     while(i < effective_length && buffer[i] >= '0' && buffer[i] <= '9'){
    
20.         b = (b << 3) + (b << 1) + (buffer[i++] - '0');
    
21.     }
    
22.     lseek(STDIN_FILENO, 0, SEEK_SET);
    
23.     unsigned long result = 0;
    
24.     effective_length = i = 0;
    
25.     while(1){
    
26.         effective_length = read(STDIN_FILENO, buffer, BufferSize);
    
27.         for(i = 0; i < effective_length; i++){
    
28.             if(buffer[i] == ' ') goto end;
    
29.             result = ((result << 3) + (result << 1) + (buffer[i] - '0')) % b;
    
30.         }
    
31.     }
    
32.     end:
    
33.     i = 12;
    
34.     effective_length = 0;
    
35.     if(result == 0){
    
36.         effective_length = 1;
    
37.         buffer[i--] = '0';
    
38.     }
    
39.     while(result){
    
40.         effective_length++;
    
41.         buffer[i--] = (result % 10) + '0';
    
42.         result /= 10;
    
43.     }
    
44.     write(STDOUT_FILENO, buffer + i + 1, effective_length);
    
45.     return 0;
    
46. }

复制代码

跳转到最佳答案楼层

dolly_yos2

应该是不需要高精度的
版本一（任意输入方式）：

1. #include <iostream>
   
2. #include <string>
   
3. int main(){
   
4.     std::string a;
   
5.     uint64_t b;
   
6.     uint64_t result = 0;
   
7.     std::cin >> a >> b;
   
8.     for(const auto c: a){
   
9.         result = ((result << 3) + (result << 1) + (c - '0')) % b;
   
10.     }
    
11.     std::cout << result;
    
12.     return 0;
    
13. }

复制代码

版本二（需要将输入重定向到文件）：

1. #include <unistd.h>
   
2. #include <sys/stat.h>
   
3. int main(){
   
4.     enum{ BufferSize = 1024 };
   
5.     struct stat status;
   
6.     unsigned char buffer[BufferSize];
   
7.     ssize_t effective_length;
   
8.     if(fstat(STDIN_FILENO, &status) == -1){
   
9.         return 1;
   
10.     }
    
11.     off_t seek_offset = status.st_size > 11 ? -11 : -status.st_size;
    
12.     if(lseek(STDIN_FILENO, seek_offset, SEEK_END) == -1){
    
13.         return 1;
    
14.     }
    
15.     effective_length = read(STDIN_FILENO, buffer, BufferSize);
    
16.     unsigned long b = 0;
    
17.     ssize_t i = 0;
    
18.     while(buffer[i++] != ' ');
    
19.     while(i < effective_length && buffer[i] >= '0' && buffer[i] <= '9'){
    
20.         b = (b << 3) + (b << 1) + (buffer[i++] - '0');
    
21.     }
    
22.     lseek(STDIN_FILENO, 0, SEEK_SET);
    
23.     unsigned long result = 0;
    
24.     effective_length = i = 0;
    
25.     while(1){
    
26.         effective_length = read(STDIN_FILENO, buffer, BufferSize);
    
27.         for(i = 0; i < effective_length; i++){
    
28.             if(buffer[i] == ' ') goto end;
    
29.             result = ((result << 3) + (result << 1) + (buffer[i] - '0')) % b;
    
30.         }
    
31.     }
    
32.     end:
    
33.     i = 12;
    
34.     effective_length = 0;
    
35.     if(result == 0){
    
36.         effective_length = 1;
    
37.         buffer[i--] = '0';
    
38.     }
    
39.     while(result){
    
40.         effective_length++;
    
41.         buffer[i--] = (result % 10) + '0';
    
42.         result /= 10;
    
43.     }
    
44.     write(STDOUT_FILENO, buffer + i + 1, effective_length);
    
45.     return 0;
    
46. }

复制代码

人造人

你有什么话要说吗？
^_^

1. sh-5.1$ cat main.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. sh-5.1$ ./main
    
14. 888333 823
    
15. 316
    
16. sh-5.1$
    

复制代码

高山

厉害，这么多关了，真是给我了个大大的惊喜。我还以为你们都不发了呢。

sfqxx

@zhangjinxuan 下一个我发，已经有经验了

元豪

高精度，不存在的~~

1. x = input().split()
   
2. print(int(x[0]) % int(x[1]))
   

复制代码

dolly_yos2

怪事，我的回答为什么会被审核，待会再看吧
题解可能需要检查一下，目前有严重的问题

sfqxx

元豪 发表于 2023-1-26 13:47
高精度，不存在的~~

准备报废电脑

zhangjinxuan

高山 发表于 2023-1-26 12:59
厉害，这么多关了，真是给我了个大大的惊喜。我还以为你们都不发了呢。

zhangjinxuan

sfqxx 发表于 2023-1-26 13:35
@zhangjinxuan 下一个我发，已经有经验了

好的，可以，自己选题哈

zhangjinxuan

dolly_yos2 发表于 2023-1-26 15:41
怪事，我的回答为什么会被审核，待会再看吧
题解可能需要检查一下，目前有严重的问题

没必要真的去算

zhangjinxuan

元豪 发表于 2023-1-26 13:47
高精度，不存在的~~

超时了~~~~~~哈哈哈哈哈
只有 60 分

红眼特效播放中！！

                               
登录/注册后可看大图

哈哈哈哈哈哈
哎呀，python，没想到你还有今天，哈哈哈哈哈哈

zhangjinxuan

元豪 发表于 2023-1-26 13:47
高精度，不存在的~~

真超时了，我搞了个数据生成器，哈哈，1e6 就超时啦~~~~

                               
登录/注册后可看大图

                               
登录/注册后可看大图

zhangjinxuan

dolly_yos2 发表于 2023-1-26 15:41
怪事，我的回答为什么会被审核，待会再看吧
题解可能需要检查一下，目前有严重的问题

严重……问题？我的题解？标程有问题？

zhangjinxuan

dolly_yos2 发表于 2023-1-26 15:41
怪事，我的回答为什么会被审核，待会再看吧
题解可能需要检查一下，目前有严重的问题

感谢提醒，我 n 忘了初始化
我真的……太尴尬……太丢人了

元豪

zhangjinxuan 发表于 2023-1-26 19:06
真超时了，我搞了个数据生成器，哈哈，1e6 就超时啦~~~~

啊这......

sfqxx

zhangjinxuan 发表于 2023-1-26 18:51
好的，可以，自己选题哈

自己选？？？？

sfqxx

                               
登录/注册后可看大图

dolly_yos2

zhangjinxuan 发表于 2023-1-26 19:11
感谢提醒，我 n 忘了初始化
我真的……太尴尬……太丢人了

第21行是不是也有一点问题？

zhangjinxuan

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

我太糊涂了

直接从 12期 那里搬过来的，有点