[CodePlus2017年12月]可做題2 數論

Description

請你求出滿足條件 a1 = i，a2 為區間 [l,r] 中的整數，且 ak mod p = m 的廣義

斐波那契數列有多少個。

Sample Input

6

2 17 68 3 23 1

1 17 68 3 57 1

5 17 68 10 11 9

5 17 68 10 71 9

10 17 68 11 12 3

10 17 68 8 6 4

Sample Output

3

1

4

1

5

9

這道題把式子推一下求一下exgcd就好了，沒什麼好說的。。。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

LL mod;
struct node {
	LL a[2][2];
	node() {memset(a, 0, sizeof(a));}
	friend node operator * (node a, node b) {
		node c;
		for(int i = 0; i < 2; i++) {
			for(int j = 0; j < 2; j++) {
				for(int k = 0; k < 2; k++) {
					(c.a[i][j] += a.a[i][k] * b.a[k][j] % mod) %= mod;
				}
			}
		} return c;
	}
} A, ans;

LL exgcd(LL a, LL b, LL &x, LL &y) {
	if(b == 0) {x = 1, y = 0; return a;}
	else {
		LL tx, ty, d = exgcd(b, a % b, tx, ty);
		x = ty, y = tx - ty * (a / b);
		return d;
	}
}

int main() {
	int tt; scanf("%d", &tt);
	while(tt--) {
		LL X, l, r, k, m;
		scanf("%lld%lld%lld%lld%lld%lld", &X, &l, &r, &k, &mod, &m);
		k -= 3; X %= mod;
		A.a[0][0] = 0; A.a[0][1] = 1;
		A.a[1][0] = 1; A.a[1][1] = 1;
		ans.a[0][0] = 1, ans.a[0][1] = 1;
		ans.a[1][0] = ans.a[1][1] = 0;
		while(k) {
			if(k & 1) ans = ans * A;
			A = A * A; k /= 2;
		} (m -= X * ans.a[0][0] % mod) %= mod;
		(m += mod) %= mod;
		LL x, y, d = exgcd(ans.a[0][1], mod, x, y);
		if(m % d != 0) {printf("0\n"); continue;}
		LL u = mod / d, hh;
		x = (x * (m / d) % u + u) % u;
		if(x >= l && x <= r) {
			x = x - u * ((x - l) / u);
			hh = (r - x) / u + 1;
		} else if(x < l){
			x = x + u * ((l - x + u - 1) / u);
			if(x > r) hh = 0;
			else hh = (r - x) / u + 1;
		} else {
			x = x - u * ((x - l + u - 1) / u);
			if(x < l) hh = 0;
			else hh = (r - x) / u + 1;
		} printf("%lld\n", hh);
	}
	return 0;
}