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

tommyyu

decimal行不行

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

zhangjinxuan

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

一帮老六

dolly_yos2

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

zhangjinxuan

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

有！
你们这帮老六

[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 就崩了（是不是我操作错了，我没用过

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

输入数据：

7565521721998976389927665831246144538921968281367235378722916219634739798727419319539391588679818592277666374722947419138792565464137328872349233178547958481656738439975357856148634247733446987756315879633952797512872145816425352818178249817618781439875717698133717912462318749761975695197526421242444711682118786267513331389328134665148473613491636727372866995863146431871535827823456288992432978864725938444874878677169753171511496329225657884249393715984636369864646899989965376515865792623613682958673541987281228861322936131615789374839753239945848124959465276383638912345255821822173695668862137631714722212386872391833643812779935843986553388133312455182377829843822421655897183957681387187486693176878979516984985271441188192655461994761434483469848167914647387631398168272618139754257894646498585977842364261194959477788649569954295633459972517429867384168541294112118359268455273499999455767741989459846291678329649697848841314917576391132422724454573757562782668489386363411845549146215341 3158

人造人

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

输入数据：

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

sh-5.1$ time ./main <<EOF
> 7565521721998976389927665831246144538921968281367235378722916219634739798727419319539391588679818592277666374722947419138792565464137328872349233178547958481656738439975357856148634247733446987756315879633952797512872145816425352818178249817618781439875717698133717912462318749761975695197526421242444711682118786267513331389328134665148473613491636727372866995863146431871535827823456288992432978864725938444874878677169753171511496329225657884249393715984636369864646899989965376515865792623613682958673541987281228861322936131615789374839753239945848124959465276383638912345255821822173695668862137631714722212386872391833643812779935843986553388133312455182377829843822421655897183957681387187486693176878979516984985271441188192655461994761434483469848167914647387631398168272618139754257894646498585977842364261194959477788649569954295633459972517429867384168541294112118359268455273499999455767741989459846291678329649697848841314917576391132422724454573757562782668489386363411845549146215341 3158
> EOF
1247

real        0m0.064s
user        0m0.021s
sys        0m0.013s
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

$ cat test.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;
}%                                                                                                                                                                                                                                                                          
$ clang++ test.cpp
$ /usr/bin/time -p timeout -v 0.5s ./a.out < input
timeout: sending signal TERM to command ‘./a.out’
real 0.50
user 0.49
sys 0.00
$ cat test2.cpp                               
#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;
}%                                                                                                                                                                                                                                                                          
$ clang++ test2.cpp                               
$ /usr/bin/time -p timeout -v 0.5s ./a.out < input
1313860644
real 0.13
user 0.13
sys 0.00
$ cat test3.cpp                                   
#include <cstdio>
#include <cstring>

char a[10000005];
int n, p;

long long eval_ans() {
        long long x = 1, avalue = 0;
        for (int i = n; i >= 1; --i) {
                long long ap = (long long)(a[i] - '0') * x;
                ap %= p;
                avalue += ap;
                avalue %= p;
                x *= 10;
                x %= p;
        }
        return avalue;
}

int main() {
        scanf("%s%d", a + 1, &p);
        n = strlen(a + 1);
        printf("%lld", eval_ans());
}
$ clang++ test3.cpp                               
$ /usr/bin/time -p timeout -v 0.5s ./a.out < input
1313860644
real 0.07
user 0.07
sys 0.00
$ cat test.c
#include <unistd.h>
#include <sys/stat.h>
#include <sys/types.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;
}%                                                                                                                                                                                                                                                                          
$ clang test.c
$ /usr/bin/time -p timeout -v 0.5s ./a.out < input
1313860644
real 0.03
user 0.02
sys 0.00