专栏文章

题解：P2613 【模板】有理数取余

MMatrixGroup时序绚乱
P2613题解参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@miq0jfg1
此快照首次捕获于
2025/12/03 20:58
3 个月前
此快照最后确认于
2025/12/03 20:58
3 个月前
查看原文

算法介绍

有理数取余是因为整数取模不能做除法而打上的一个补丁。
对于正整数 mm 和有理数 xx，若 x=pqx=\dfrac pq，其中 p,qp,q 互质，若 q,mq,m 互质，我们定义 xx 模 mm 的结果为唯一满足 0≤r<m0\le r<m 的整数 rr 满足 rq≡p(modm)rq\equiv p\pmod m。可以证明这是存在且唯一的，并且就算 p,qp,q 不互质，只要 q,mq,m 互质，这个结果是不变的。
可以证明，有理数取模就可以加减乘除，其中除要满足除数与 mm 互质（若 mm 为素数，就是要求非零）。这里主要介绍算法，所以略去性质相关的证明。
根据题意，给定 p=19 260 817p=19\, 260\, 817 和一个有理数 ab\dfrac ab，我们要找到唯一一个 0≤r<p0\le r<p 满足 rb≡a(modp)rb\equiv a\pmod p。首先这个式子只和 a,ba,b 在  mod p{}\bmod p 意义下的值相关，因此可以同时读入和取模。接下来只需要枚举 rr 就可以在 O(p)O(p) 的时间内通过本题。

正确性证明

这里主要来证一下 a,ba,b 不互质的情况下也是对的。若 a,ba,b 同乘 dd，因为 rb≡a(modp)rb\equiv a\pmod p，故 rbd≡ad(modp)rbd\equiv ad\pmod p，即用 ad,bdad,bd 算的也是对的。
复杂度因为 0≤r<p0\le r<p 的整数 rr 只有 pp 个，所以复杂度是 O(p)O(p) 的（忽略读入时间）。

代码实现

本题还要求若 b≡0,a≢0(modp)b\equiv 0,a\not\equiv0\pmod p 时输出 Angry!，此时对应了方程无解（除以零）的情况，因此找不到的时候输出即可。
CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=19260817;
ll getint()
{
    char c=getchar();
    while(!isdigit(c)) c=getchar();
    ll ans=0;
    while(isdigit(c))
    {
        ans=(ans<<1)+(ans<<3)+c-'0';
        ans%=mod;
        c=getchar();
    }
    return ans;
}
int main()
{
    ll a=getint();
    ll b=getint();
    for(int i=0;i<mod;++i)
    {
        if(i*b%mod==a)
        {
             printf("%d\n",i);
             return 0;
        }
    }
    printf("Angry!\n");
    return 0;
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...