信息学奥赛一本通 1080:余数相同问题 | OpenJudge NOI 小学奥数/2.1 7647:余数相同问题
【題目鏈接】
ybt 1080:余數(shù)相同問(wèn)題
OpenJudge NOI 2.1 7647:余數(shù)相同問(wèn)題
OpenJudge NOI 小學(xué)奧數(shù) 7647:余數(shù)相同問(wèn)題
【題目考點(diǎn)】
1. 枚舉
【解題思路】
題目給出a,b,c小于等于10610^6106,可行的解一定小于10610^6106,可以考慮用枚舉解法。
枚舉解法
x從2循環(huán)到1000000,分別求a % x, b % x, c % x,如果三者的結(jié)果相等,那么輸出x,結(jié)束程序。
處理后的枚舉解法
已知a,b,c除以數(shù)x后得到的余數(shù)相同,可以有方程組
a÷x=q1??ra \div x = q_1 \cdots\cdots ra÷x=q1???r
b÷x=q2??rb \div x = q_2 \cdots\cdots rb÷x=q2???r
c÷x=q2??rc \div x = q_2 \cdots\cdots rc÷x=q2???r
其中x,q1,q2,q3,rx,q_1,q_2,q_3,rx,q1?,q2?,q3?,r都是整數(shù)
方程兩兩相減,調(diào)整后可得
a?bx=q1?q2\frac{a-b}{x} = q_1 - q_2xa?b?=q1??q2?
b?cx=q2?q3\frac{b-c}{x} = q_2 - q_3xb?c?=q2??q3?
由于不清楚a,b,c的大小關(guān)系。為了使參與運(yùn)算的表達(dá)式都是非負(fù)數(shù),對(duì)等式兩側(cè)取絕對(duì)值,有
∣a?b∣x=∣q1?q2∣\frac{|a-b|}{x} = |q_1 - q_2|x∣a?b∣?=∣q1??q2?∣
∣b?c∣x=∣q2?q3∣\frac{|b-c|}{x} = |q_2 - q_3|x∣b?c∣?=∣q2??q3?∣
等式右側(cè)的都是整數(shù)值,因而左側(cè)必然可以整除,即∣a?b∣|a-b|∣a?b∣可以整除xxx,且∣b?c∣|b-c|∣b?c∣可以整除xxx。
題目要求最小的x,即求∣a?b∣|a-b|∣a?b∣與∣b?c∣|b-c|∣b?c∣的最小公約數(shù)。
具體方法,還是枚舉。x從2循環(huán)到1000000,看哪個(gè)x能同時(shí)被∣a?b∣|a-b|∣a?b∣和∣b?c∣|b-c|∣b?c∣整除。
注意:不能寫(xiě)為x從2循環(huán)到min(∣a?b∣,∣b?c∣)min(|a-b|,|b-c|)min(∣a?b∣,∣b?c∣),因?yàn)檫@兩個(gè)差值可能為0,從2開(kāi)始循環(huán)的話,會(huì)導(dǎo)致循環(huán)體一次都不執(zhí)行,以至于沒(méi)有輸出。
【題解代碼】
解法1:枚舉
#include<bits/stdc++.h> using namespace std; int main() {int x, a, b, c;cin>>a>>b>>c;int am, bm, cm;//a,b,c對(duì)x取模的值for(x = 2; x <= 1000000; ++x){am = a % x;bm = b % x;cm = c % x;if(am == bm && bm == cm && cm == am){cout<<x;//只求最小值,只要找到一個(gè)符合條件的x即可break;}}return 0; }解法2:處理后的枚舉
#include<bits/stdc++.h> using namespace std; int main() {int x, a, b, c;cin>>a>>b>>c;int ab = abs(a - b), bc = abs(b - c);for(int x = 2; x <= 1000000; x++){if(ab % x == 0 && bc % x == 0){cout<<x;break;}}return 0; }總結(jié)
以上是生活随笔為你收集整理的信息学奥赛一本通 1080:余数相同问题 | OpenJudge NOI 小学奥数/2.1 7647:余数相同问题的全部?jī)?nèi)容,希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇: 信息学奥赛一本通(1171:大整数的因子
- 下一篇: 信息学奥赛一本通(1200:分解因数)