SRM 537 DIV1 275 KingXNewCurrency

問題

　正の整数A, B, Xが与えられる。任意の非負正数p, qに対してAp + Bq = Xp' + Yq'となるような非負正数p', q'が存在するような正の整数Yの個数を求めよ。

方針

　あるYにおいて、任意の非負整数p, qに対して問題の等式が成り立つような(p', q')が存在するとする。このとき特に(p, q) = (1, 0)とすると、A = Xp' + Yq'が成り立つ。同様に、(p, q) = (0, 1)のときは、B = Xp' + Yq'が成り立つ。つまり、AとBは、X, Yの非負線形結合で表すことができる。

　逆に、AとBの両方がX, Yの非負線形結合で表されるとする。このとき、明らかに任意のp, qに対して問題の等式を満たすp', q'が存在する。

　よって、問題の等式を満たすYの個数は、A, BをX, Yの非負線形結合で表すことのできるようなYの個数と同じ。

ソースコード

　O(N²)バージョンと、拡張ユークリッド互除法を用いたO(N (log(N))²)バージョンを載せて起きます。今回の問題では、O(N²)で十分です。

view plainprint?

1. class KingXNewCurrency {  
2. public:  
3.     int howMany(int A, int B, int X) {  
4.         if (A % X == 0 && B % X == 0)  
5.             return -1;  
6.   
7.         int ret = 0;  
8.         for (int Y = 1; Y <= 200; Y++) {  
9.             bool cana = false;  
10.             bool canb = false;  
11.   
12.             for (int t = A; t >= 0; t -= X)  
13.                 if (t % Y == 0)  
14.                     cana = true;  
15.   
16.             for (int t = B; t >= 0; t -= X)  
17.                 if (t % Y == 0)  
18.                     canb = true;  
19.   
20.             if (cana && canb)  
21.                 ++ret;  
22.         }  
23.   
24.         return ret;  
25.     }  
26. };  

class KingXNewCurrency {
public:
    int howMany(int A, int B, int X) {
        if (A % X == 0 && B % X == 0)
            return -1;

        int ret = 0;
        for (int Y = 1; Y <= 200; Y++) {
            bool cana = false;
            bool canb = false;

            for (int t = A; t >= 0; t -= X)
                if (t % Y == 0)
                    cana = true;

            for (int t = B; t >= 0; t -= X)
                if (t % Y == 0)
                    canb = true;

            if (cana && canb)
                ++ret;
        }

        return ret;
    }
};

view plainprint?

1. int extGcd (int a, int b, int &x, int &y) {  
2.     if (b == 0) {  
3.         x = 1;  
4.         y = 0;  
5.         return a;  
6.     }  
7.     int d = extGcd(b, a%b, y, x);  
8.     y -= a/b * x;  
9.     return d;  
10. }  
11.   
12. class KingXNewCurrency {  
13.     bool canMake(int A, int x, int y, int g, int p, int q) {  
14.         int lcm = x * y / g;  
15.         int dp = lcm / x;  
16.         int dq = lcm / y;  
17.         p = A * p / g;  
18.         q = A * q / g;  
19.   
20.         if (p < 0) {  
21.             int add = (-p + dp - 1) / dp;  
22.             p += add * dp;  
23.             q -= add * dq;  
24.         }  
25.         else if (q < 0) {  
26.             int add = (-q + dq - 1) / dq;  
27.             p -= add * dp;  
28.             q += add * dq;  
29.         }  
30.   
31.         return p >= 0 && q >= 0;  
32.     }  
33.   
34. public:  
35.     int howMany(int A, int B, int X) {  
36.         if (A % X == 0 && B % X == 0)  
37.             return -1;  
38.   
39.         int p, q, g, ret = 0;  
40.         bool cana, canb;  
41.         for (int Y = 1; Y <= 200; Y++) {  
42.             g = extGcd(X, Y, p, q);  
43.   
44.             cana = (A % g) ? false : canMake(A, X, Y, g, p, q);  
45.             canb = (B % g) ? false : canMake(B, X, Y, g, p, q);  
46.             if (cana && canb)  
47.                 ++ret;  
48.         }  
49.   
50.         return ret;  
51.     }  
52. };  

int extGcd (int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = extGcd(b, a%b, y, x);
    y -= a/b * x;
    return d;
}

class KingXNewCurrency {
    bool canMake(int A, int x, int y, int g, int p, int q) {
        int lcm = x * y / g;
        int dp = lcm / x;
        int dq = lcm / y;
        p = A * p / g;
        q = A * q / g;

        if (p < 0) {
            int add = (-p + dp - 1) / dp;
            p += add * dp;
            q -= add * dq;
        }
        else if (q < 0) {
            int add = (-q + dq - 1) / dq;
            p -= add * dp;
            q += add * dq;
        }

        return p >= 0 && q >= 0;
    }

public:
    int howMany(int A, int B, int X) {
        if (A % X == 0 && B % X == 0)
            return -1;

        int p, q, g, ret = 0;
        bool cana, canb;
        for (int Y = 1; Y <= 200; Y++) {
            g = extGcd(X, Y, p, q);

            cana = (A % g) ? false : canMake(A, X, Y, g, p, q);
            canb = (B % g) ? false : canMake(B, X, Y, g, p, q);
            if (cana && canb)
                ++ret;
        }

        return ret;
    }
};