NOIP 2017 Day1 T1 小凱的疑惑

luogu題面

小學奧數呵呵

在考場上40分鐘沒證出來（數學太差），運氣好看到了規律...

來一波證明：

定義 f(a,b) 表示在 gcd(a,b)==1 情況下的答案。

貝祖定理 易證：對於 gcd(c,b)==1，c > a , 有 f(c,b) = f(a,b) + (c-a)*(b-1)

因為我們已知：f(a,b) == f(b,a) ，且 gcd(a,b) == 1

那麼我們不妨令 b 為奇數（兩數至少一數為奇數）

那麼，f(a,b) == f(2,b) + (a-2)*(b-1)

接下來，同理我們解 f(2,b) = f(b,2) = f(3,2) + (b-3)*(2-1) == f(3,2) + (b-3)

由於我們已知：f(2,3) == 1

所以，f(a,b) = f(2,b) + (a-2)*(b-1) = f(3,2) + (b-3) + (a-2)*(b-1) = 1 + b-3 + (ab-2b-a+2) == ab-b-a

證畢。

代碼...沒多大意義啊...

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long a,b;  // 不開 LL 會炸掉
    scanf("%lld%lld",&a,&b);
    printf("%lld",a*b-a-b);
    return 0;
}

%%% Dalao 的 ex_gcd

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b){
    return b == 0 ? a : gcd(b, a % b);
}
void ex_gcd(ll a, ll b, ll &x, ll &y){
    if(b == 0){
        x = 1, y = 0; return;
    }
    ex_gcd(b, a % b, y, x);
    y -= (a / b) * x;
}
ll a, b;
int main(){
    cin >> a >> b;
    if(a > b) swap(a, b); 
    ll x, y;
    ex_gcd(a, b, x, y);
    if(x > 0){
        swap(a, b);
        swap(x, y);
    }
    ll tmp = (-x) / b;
    x = x + tmp * b;
    y = y - tmp * a;
    while(x < 0) x = x + b, y = y - a;
    while(x > 0) x = x - b, y = y + a;
    ll ans;
    ll xx2 = x + b;
    ans = a * (xx2 - 1) + b * (y - 1);
    cout << ans - 1 << endl;
    return 0;
}

By  The_Seventh

2017-12-23  19:32:14