#37717: 避開 overflow


proglohas@gmail.com (david)

學校 : 不指定學校
編號 : 221623
來源 : [114.42.166.68]
最後登入時間 :
2024-07-04 17:52:44
a810. 1. 倍數關係 -- 102學年度高雄市資訊學科能力競賽複賽 | From: [122.117.95.179] | 發表日期 : 2023-10-01 22:32

ll lcm(ll m, ll n)
{
    ll g = __gcd(m, n);
    return (m / g) * n;
}

r -= b / (lcm(x, y));

這裡有個呼叫 lcm 時,如果 x, y 太大又互質時會 overflow
可以改個地方避開這個問題

ll lcm(ll m, ll n, ll y)
{
    ll g = __gcd(m, n);
    ll mg = m / g;
    if (y / n < mg) return y + 1;
    return (m / g) * n;
}

r -= b / (lcm(x, y, b));

 
ZeroJudge Forum