点击打开vjudge题目链接

这道题可以暴力枚举a和b,做出来大概1S左右,不再赘述。如果只枚举a,那么可以用扩展欧几里得定理求得b,具体公式为:

x3 = (a*a*x1 + a*b) % 10001 + b % 10001, 化简为:x3 – 10001k = a*a*x1 + b*(a+1),再化简为:b*(a+1) + 10001*k = x3-a*a*x1。

这样a和x1,x3都是已知的,求出b和k来,用a和b验证整个数列是否符合即可。

直接暴力代码:

#include <bits/stdc++.h>
using namespace std;

const int mod = 10001;
int n, v[205];

void solve() {
    for(int a = 0; a < mod; ++a) {
        for(int b = 0; b < mod; ++b) {
            int i;
            for(i = 2; i <= 2*n; ++i) {
                if(i & 1) {
                    if(v[i] != (a * v[i-1] % mod + b) % mod)
                        break;
                }
                else v[i] = (a * v[i-1] % mod + b) % mod;
            }
            if(i == 2 * n + 1) {
                for(i = 2; i <= 2*n; i += 2)
                    printf("%d\n", v[i]);
                return;
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &v[2*i-1]);
    solve();
    return 0;
}

暴力+扩展欧几里得定理:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod = 10001;
ll n, v[205];

// ax + by = gcd(a, b) = g;
void exgcd(ll a, ll b, ll &g, ll &x, ll &y) {
    if(!b) { g = a; x = 1; y = 0; }
    else { exgcd(b, a%b, g, y, x); y -= x*(a/b); }
}

bool judge(ll a, ll b) {
    for(int i = 2; i <= 2*n; ++i) {
        if(i & 1) {
            if(v[i] != (v[i-1] * a % mod + b) % mod)
                return false;
        }
        else v[i] = (v[i-1] * a % mod + b) % mod;
    }
    return true;
}


int main() {
    scanf("%lld", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%lld", &v[2*i-1]);
    for(ll a = 0; a < mod; ++a) {
        ll b, k, g, c = v[3]-a*a*v[1];
        exgcd(mod, a+1, g, k, b);
        if(c % g) continue;
        b = b * c / g;
        if(judge(a, b % mod)) {
            for(int i = 2; i <= 2*n; i += 2)
                printf("%lld\n", v[i]);
            break;
        }
    }
    return 0;
}

欢迎留言