Author: lllyouo
Date: 20250702
tag: 同余、快速幂
link: https://www.luogu.com.cn/problem/P2818

问题描述

link

分析

计算 $m\mathrm{\%}n$。根据同余的同加和同乘性可知：

$a\equiv (a\ast 10+c)(\mathrm{mod}m)$

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n, ans;
    string s;
    cin >> n >> s;

    for (int i = 0; i < s.size(); i++) {
        ans = (ans * 10 + s[i] - '0') % n;
    }

    if (ans == 0) {
        cout << n << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}