杭电多校第二场 1006 The Oculus 题解

题目大意

给你一个从1,2开始的斐波那契数列，给你三个数$a,b,c$，以及三个数用斐波那契数列的表示形式，这个c是修改后的c，原本c等于a*b，但是将其中一位的1替换成了0，问你是哪一位替换了。

$\large b_1\times F_1+b_2\times F_2+\dots+b_n\times F_n=x$

其中的$b_n\in {0,1}$。

解题思路

说实话，这个题目原题好吓人。

看了一下没看懂，就没去做这个题目了。

补题的时候发现其实这个应该是签到题。

我们已经知道了a和b的值，只需要用这两个数的乘积减去c，然后判断这个差值是等于哪一位斐波那契数列的值即可。

即需要找到满足使斐波那契数列两两不相同的模数P，使$F_kmodp=(a*b-c)modP$。

这一步应该是这个题的难点了。

（反正我是没想到。。

看了一个大佬的题解，貌似可以用暴力枚举，求出一个值3799912185593857。

但是其他题解都是用的$2^{64}$，即ull的自然溢出。

但是我不知道为啥$2^{64}$就能满足这个条件。。

可能对于大佬来说这就是常识吧。。

像上场比赛的1005一样，一开始不知道为啥n可以摸mod-1，后来一查才发现，是用了欧拉降幂。。

我太弱了。。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int maxn = 2e6 + 5;
ull F[maxn];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t;
	cin >> t;
	F[1] = 1, F[2] = 2;
	for (int i = 3; i < maxn; i++)
		F[i] = F[i - 1] + F[i - 2];
	while (t--) {
		int A, B, C;
		ull a, b, c;
		a = b = c = 0;
		cin >> A;
		for (int i = 1; i <= A; i++) {
			int x;
			cin >> x;
			if (x)	a += F[i];
		}
		cin >> C;
		for (int i = 1; i <= C; i++) {
			int x;
			cin >> x;
			if (x)	b += F[i];
		}
		cin >> C;
		for (int i = 1; i <= C; i++) {
			int x;
			cin >> x;
			if (x)	c += F[i];
		}
		ull ans = a * b;
		int i = 1;
		while (ans - c != F[i])	i++;
		cout << i << endl;
	}
}