2010-1153

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题目大意：给定两个整数a，b满足0 < b-a < 1+2a^1/2^, 求[(a^1/2^ + b^1/2^)^n^] % (2(a+b)).(n为偶数, [x]为Gauss函数)

由条件知：0 < b^1/2^ - a^1/2^ < 1

设x,,n,, = (b^1/2^ + a^1/2^)^2n^ = (a + b + 2(ab)^1/2^)^n^,

y,,n,, = (b^1/2^ - a^1/2^)^2n^ = (a + b - 2(ab)^1/2^)^n^,

z,,n,, = x,,n,, + y,,n,,

x,,1,, = a + b + 2(ab)^1/2^, y,,1,, = a + b - 2(ab)^1/2^

则由x,,1,,和y,,1,,为根的的一元二次方程为x^2^ - 2(a + b)x + (a - b)^2^ = 0

两端同乘以x^n^得：x^n+2^ - 2(a + b)x^n+1^ + (a - b)^2^x^n^ = 0

当x = x,,1,,时：即x,,n+2,, - 2(a + b)x,,n,, + (a - b)^2^x,,n,, = 0

当x = y,,1,,时：即y,,n+2,, - 2(a + b)y,,n,, + (a - b)^2^y,,n,, = 0

以上两式相加得： z,,n+2,, - 2(a + b)z,,n,, + (a - b)^2^z,,n,, = 0

即z,,n+2,, = 2(a + b)z,,n,, - (a - b)^2^z,,n,,

且z,,0,, = 2, z,,1,, = 2(a + b)

由递推式知：z,,n,,都为整数

又0 < b^1/2^ - a^1/2^ < 1, 即0 < y,,n,, < 1

所以z,,n,, - 1 = [(a^1/2^ + b^1/2^)^n^]

题目所求即: z,,n/2,, - 1 mod (2(a + b))

设m = 2(a + b)

z的递推式两端同时对m取余得到模递推式:

z,,n+2,, ≡ -(a - b)^2^x,,n,, (mod m)

又x,,0,,和x,,1,,是已知的, 按上式即可求得结果

具体代码如下:
{{{
#!python
#include <cstdio>
using namespace std;

int f(int base, int exp, int m)
{
    int res = 1;

    while (exp != 0)
    {
        if (exp % 2 == 1)
        {
                   res = ((res % m) * (base % m)) % m;
        }

        base = ((base % m) * (base % m)) % m;

        exp /= 2;
    }

    return res;
}

int main()
{
    int a;
    int b;
    int n;
    int m;
    int i;
    int j;
    int k;
    int t;
    int mod;
    int res;
    int base;
    int exp;

    while (scanf("%d %d %d", &a, &b, &n) != EOF)
    {
        if (n % 4 != 0)
        {
            printf("%d\n", 2 * (a + b) - 1);
        }
        else
        {
            mod = 2 * (a + b);
            base = a - b;
            base %= mod;
            base *= base;
            base *= -1;
            base %= mod;
            base += mod;
            base %= mod;//printf("base: %d\n", base);
            exp = n / 4;
            res = f(base, exp, mod);
            res *= 2;
            res -= 1;
            res += mod;
            res %= mod;
            printf("%d\n", res);
        }
    }

    return 0;
}
}}}
[by delta_4d]

题目大意：给定两个整数a，b满足0 < b-a < 1+2a^1/2, 求[(a^1/2 + b^1/2)ⁿ] % (2(a+b)).(n为偶数, [x]为Gauss函数)

由条件知：0 < b^1/2 - a^1/2 < 1

设x_n = (b^1/2 + a^1/2)²ⁿ = (a + b + 2(ab)^1/2)ⁿ,

y_n = (b^1/2 - a^1/2)²ⁿ = (a + b - 2(ab)^1/2)ⁿ,

z_n = x_n + y_n

x₁ = a + b + 2(ab)^1/2, y₁ = a + b - 2(ab)^1/2

则由x₁和y₁为根的的一元二次方程为x² - 2(a + b)x + (a - b)² = 0

两端同乘以xⁿ得：xⁿ⁺² - 2(a + b)xⁿ⁺¹ + (a - b)²xⁿ = 0

当x = x₁时：即x_n+2 - 2(a + b)x_n + (a - b)²x_n = 0

当x = y₁时：即y_n+2 - 2(a + b)y_n + (a - b)²y_n = 0

以上两式相加得： z_n+2 - 2(a + b)z_n + (a - b)²z_n = 0

即z_n+2 = 2(a + b)z_n - (a - b)²z_n

且z₀ = 2, z₁ = 2(a + b)

由递推式知：z_n都为整数

又0 < b^1/2 - a^1/2 < 1, 即0 < y_n < 1

所以z_n - 1 = [(a^1/2 + b^1/2)ⁿ]

题目所求即: z_n/2 - 1 mod (2(a + b))

设m = 2(a + b)

z的递推式两端同时对m取余得到模递推式:

z_n+2 ≡ -(a - b)²x_n (mod m)

又x₀和x₁是已知的, 按上式即可求得结果

具体代码如下:

#include <cstdio>
using namespace std;
int f(int base, int exp, int m)
{
    int res = 1;
    while (exp != 0)
    {
        if (exp % 2 == 1)
        {
                   res = ((res % m) * (base % m)) % m;
        }
        base = ((base % m) * (base % m)) % m;
        exp /= 2;
    }
    return res;
}
int main()
{
    int a;
    int b;
    int n;
    int m;
    int i;
    int j;
    int k;
    int t;
    int mod;
    int res;
    int base;
    int exp;
    while (scanf("%d %d %d", &a, &b, &n) != EOF)
    {
        if (n % 4 != 0)
        {
            printf("%d\n", 2 * (a + b) - 1);
        }
        else
        {
            mod = 2 * (a + b);
            base = a - b;
            base %= mod;
            base *= base;
            base *= -1;
            base %= mod;
            base += mod;
            base %= mod;//printf("base: %d\n", base);
            exp = n / 4;
            res = f(base, exp, mod);
            res *= 2;
            res -= 1;
            res += mod;
            res %= mod;
            printf("%d\n", res);
        }
    }
    return 0;
}

[by delta_4d]