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

zhangjinxuan

上一关：细胞分裂

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

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

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

题目是这样的：

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

输入格式

A B

输出格式

【A % B 的结果】

输入样例

888333 823

输出样例

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

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

#include <iostream>
#include <string>
int main(){
    std::string a;
    uint64_t b;
    uint64_t result = 0;
    std::cin >> a >> b;
    for(const auto c: a){
        result = ((result << 3) + (result << 1) + (c - '0')) % b;
    }
    std::cout << result;
    return 0;
}

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

#include <unistd.h>
#include <sys/stat.h>
int main(){
    enum{ BufferSize = 1024 };
    struct stat status;
    unsigned char buffer[BufferSize];
    ssize_t effective_length;
    if(fstat(STDIN_FILENO, &status) == -1){
        return 1;
    }
    off_t seek_offset = status.st_size > 11 ? -11 : -status.st_size;
    if(lseek(STDIN_FILENO, seek_offset, SEEK_END) == -1){
        return 1;
    }
    effective_length = read(STDIN_FILENO, buffer, BufferSize);
    unsigned long b = 0;
    ssize_t i = 0;
    while(buffer[i++] != ' ');
    while(i < effective_length && buffer[i] >= '0' && buffer[i] <= '9'){
        b = (b << 3) + (b << 1) + (buffer[i++] - '0');
    }
    lseek(STDIN_FILENO, 0, SEEK_SET);
    unsigned long result = 0;
    effective_length = i = 0;
    while(1){
        effective_length = read(STDIN_FILENO, buffer, BufferSize);
        for(i = 0; i < effective_length; i++){
            if(buffer[i] == ' ') goto end;
            result = ((result << 3) + (result << 1) + (buffer[i] - '0')) % b;
        }
    }
    end:
    i = 12;
    effective_length = 0;
    if(result == 0){
        effective_length = 1;
        buffer[i--] = '0';
    }
    while(result){
        effective_length++;
        buffer[i--] = (result % 10) + '0';
        result /= 10;
    }
    write(STDOUT_FILENO, buffer + i + 1, effective_length);
    return 0;
}

跳转到最佳答案楼层

dolly_yos2

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

#include <iostream>
#include <string>
int main(){
    std::string a;
    uint64_t b;
    uint64_t result = 0;
    std::cin >> a >> b;
    for(const auto c: a){
        result = ((result << 3) + (result << 1) + (c - '0')) % b;
    }
    std::cout << result;
    return 0;
}

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

#include <unistd.h>
#include <sys/stat.h>
int main(){
    enum{ BufferSize = 1024 };
    struct stat status;
    unsigned char buffer[BufferSize];
    ssize_t effective_length;
    if(fstat(STDIN_FILENO, &status) == -1){
        return 1;
    }
    off_t seek_offset = status.st_size > 11 ? -11 : -status.st_size;
    if(lseek(STDIN_FILENO, seek_offset, SEEK_END) == -1){
        return 1;
    }
    effective_length = read(STDIN_FILENO, buffer, BufferSize);
    unsigned long b = 0;
    ssize_t i = 0;
    while(buffer[i++] != ' ');
    while(i < effective_length && buffer[i] >= '0' && buffer[i] <= '9'){
        b = (b << 3) + (b << 1) + (buffer[i++] - '0');
    }
    lseek(STDIN_FILENO, 0, SEEK_SET);
    unsigned long result = 0;
    effective_length = i = 0;
    while(1){
        effective_length = read(STDIN_FILENO, buffer, BufferSize);
        for(i = 0; i < effective_length; i++){
            if(buffer[i] == ' ') goto end;
            result = ((result << 3) + (result << 1) + (buffer[i] - '0')) % b;
        }
    }
    end:
    i = 12;
    effective_length = 0;
    if(result == 0){
        effective_length = 1;
        buffer[i--] = '0';
    }
    while(result){
        effective_length++;
        buffer[i--] = (result % 10) + '0';
        result /= 10;
    }
    write(STDOUT_FILENO, buffer + i + 1, effective_length);
    return 0;
}

人造人

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

sh-5.1$ cat main.cpp
#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::cpp_int;

int main() {
    cpp_int a, b;
    std::cin >> a >> b;
    std::cout << a % b << std::endl;
    return 0;
}
sh-5.1$ ./main
888333 823
316
sh-5.1$

高山

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

sfqxx

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

元豪

高精度，不存在的~~

x = input().split()
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期 那里搬过来的，有点