NC19017. Fibonacci
描述
输入描述
The first line contains an integer T indicating the number of test cases. Then for each test case, a line consists of two integers x(0) and p where 0 ≤ x(0) ≤ 109 and 1 ≤ p ≤ 200000.
输出描述
For each test, output the minimum n in a line, or −1 if it is impossible.
示例1
输入:
5 6 4 8 11 9 11 12 11 13 11
输出:
3 3 -1 1 1
说明:
In the first case, x(0) = 6 ≡ 2 (mod 4), x(1) = f(6) = 8 ≡ 0 (mod 4) and x(2) = f(8) = 21 ≡ 1 (mod 4), and therefore x(3) = f(21) = 10946 ≡ 2 (mod 4).C++11(clang++ 3.9) 解法, 执行用时: 1216ms, 内存消耗: 1852K, 提交时间: 2018-11-22 14:36:17
# include <cstdio>
# include <cstring>
# include <vector>
# include <algorithm>
# include <ctime>
using namespace std;
# define REP_0(i, n) for (int i = 0; i < n; ++ i)
# define RST(a) memset (a, 0, sizeof (a))
typedef long long ll;
int next_int () {
char c; int i;
for (c = getchar (); c < '0' || c > '9'; c = getchar ());
for (i = c - '0', c = getchar (); c >= '0' && c <= '9'; i = i * 10 + c - '0', c = getchar ());
return i;
}
ll gcd (ll a, ll b) { return !b ? a : gcd (b, a % b); }
int pr (int a, int z, int p) { int s = 1; do { if (z & 1) s = 1ll * s * a % p; a = 1ll * a * a % p; } while (z >>= 1); return s; }
struct Matrix { ll a[2][2]; Matrix () { RST (a); } };
Matrix getI () { Matrix a; REP_0 (i, 2) a.a[i][i] = 1; return a; }
Matrix getA () {
Matrix a;
a.a[0][0] = 1;
a.a[0][1] = 1;
a.a[1][0] = 1;
return a;
}
namespace Mat {
int mod;
Matrix operator* (const Matrix& a, const Matrix& b) {
Matrix c;
REP_0 (i, 2) REP_0 (k, 2) REP_0 (j, 2) c.a[i][j] += a.a[i][k] * b.a[k][j];
REP_0 (i, 2) REP_0 (j, 2) c.a[i][j] %= mod;
return c;
}
Matrix pr (Matrix a, int z) {
Matrix s = getI ();
do { if (z & 1) s = s * a; a = a * a; } while (z >>= 1);
return s;
}
}
int fib (int n, int mod) {
if (n == 0) return 0;
Mat::mod = mod;
Matrix g = Mat::pr (getA (), n - 1);
return g.a[0][0];
}
int legendre (int a, int p) { return pr (a, (p - 1) / 2, p) == 1 ? 1 : -1; }
vector <int> get_factor (int n) {
vector <int> fac;
for (int i = 1; i * i <= n; ++ i) if (n % i == 0) {
fac.push_back (i);
if (i * i != n) fac.push_back (n / i);
}
return fac;
}
int find_loop_prime (int p) {
if (p == 2) return 3;
if (p == 3) return 8;
if (p == 5) return 20;
int ans;
vector <int> fac = legendre (5, p) == 1 ? get_factor (ans = p - 1) : get_factor (ans = 2 * (p + 1));
for (int d : fac) if (fib (d, p) == 0 && fib (d + 1, p) == 1 && d < ans) ans = d;
//printf ("!fp %d %d\n", p, ans);
return ans;
}
int find_loop (int n) {
vector <int> li;
for (int i = 2; i * i <= n; ++ i) if (n % i == 0) {
int res = find_loop_prime (i); n /= i;
while (n % i == 0) n /= i, res *= i;
li.push_back (res);
}
if (n != 1) li.push_back (find_loop_prime (n));
ll ans = 1;
//printf ("[");
for (int d : li) ans = ans / gcd (ans, d) * d;//, printf ("%d ", d);
//printf ("]\n");
// printf("!!!%d %d\n", n, ans);
return ans;
}
int vis[1001000];
void helper0 () {
while (true) {
int mod;
int t; scanf ("%d%d", &t, &mod);
printf ("%d\n", fib (t, mod));
}
}
void helper1 () {
static bool vv[201000];
int s, mod;
scanf ("%d%d", &s, &mod);
for (int x = fib (s, mod); !vv[x]; x = fib (x, mod))
printf ("%d ", x), vv[x] = true;
}
int solve (const int x0, const int mod) {
int cur, next = mod;
vector <int> li;
do {
cur = next;
li.push_back (cur);
next = find_loop (cur);
} while (next != cur);
const int fin = li.back ();
const int len = li.size ();
REP_0 (i, fin) vis[i] = 0;
for (int x = fib (x0 % fin, fin), id = 0; vis[x] == 0; x = fib (x, fin)) /*printf ("!%d ", x),*/ vis[x] = ++ id;
//puts ("");
int ans = -1;
REP_0 (i, len) {
//printf ("%d ", li[i]);
int x = x0;
for (int j = i; j >= 0; -- j) x = fib (x, li[j]);
//printf ("!%d %d\n", i, x);
if (x == x0 % mod) {
ans = i + 1;
break;
}
}
//printf ("---\n");
if (ans == -1) {
REP_0 (i, fin) if (vis[i] != 0) {
int x = i;
//if (x == x0 % mod) printf ("vis%d(%d): ", i, vis[i]);
for (auto it = li.rbegin (); it != li.rend (); ++ it) {
x = fib (x, *it);
//printf ("%d ", x);
}
//puts ("");
if (x == x0 % mod) {
if (ans == -1 || ans > len + vis[i]) {
ans = len + vis[i];
}
}
}
}
return ans;
}
void helper2 () {
int mod;
scanf ("%d", &mod);
for (int i = 900000000; ; ++ i) {
//if (solve (i, mod) >= 3000) printf ("%d %d\n", i, mod);
if (solve (i, mod) >= 10) printf ("%d %d\n", i, mod);
//if (i % 1000 == 0) printf ("proc(%d)\n", i);
}
}
int main () {
for (int T = next_int (); T; -- T) {
const int x0 = next_int ();
const int mod = next_int ();
printf ("%d\n", solve (x0, mod));
//printf ("!!(%d %d)\n", fib(fib (x0, 91200), mod), x0% mod);
}
fprintf(stderr,"%.2f s\n",clock()*1.0/CLOCKS_PER_SEC);
return 0;
}
C++14(g++5.4) 解法, 执行用时: 2424ms, 内存消耗: 908K, 提交时间: 2019-10-30 09:24:59
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <unordered_map>
#include <vector>
#include <cstring>
#include <unordered_set>
using namespace std;
typedef unsigned long long ll;
namespace Fibonacci_loop{
const int M = 2;
ll Matrix_mod;
struct Matrix{
ll v[M][M];
Matrix() {memset(v, 0, sizeof(v));}
void MatrixI() {
memset(v, 0, sizeof(v));
for (int i = 0; i < M ; i++)
v[i][i] = 1;
}
Matrix operator*(const Matrix &a) const{
Matrix res;
for (int i = 0; i < M ; i ++)
for (int j = 0; j < M; j ++)
for (int k =0; k < M ; k++)
(res.v[i][k] += this->v[i][j] * a.v[j][k]) %= Matrix_mod;
return res;
}
}A;
ll calc(ll x, ll y, ll mod) {
ll z = 1;
x %= mod;
while (y) {
if (y & 1) (z *= x) %= mod;
(x *= x) %= mod, y/= 2;
}
return z;
}
Matrix calc(Matrix a, ll n, ll mod) {
Matrix_mod = mod;
Matrix res;
res.MatrixI();
while (n) {
if (n & 1) res = res * a;
a = a * a, n /= 2;
}
return res;
}
bool legendre(ll a, ll p) {//判断a在p里是否有二次剩余
return calc(a, (p - 1) >> 1, p) == 1;
}
ll fib(ll n, ll p) {
Matrix a = calc(A, n, p);
return a.v[1][0];
}
bool isloop(ll n, ll p) {
Matrix a = calc(A, n, p);
return a.v[1][0] == 0 && a.v[1][1] == 1 ;
}
ll get_prime_loop(ll p) {
if (p == 2) return 3;
if (p == 3) return 8;
if (p == 5) return 20;
ll v;
if (legendre(5, p))
v = p - 1;
else
v = 2 * (p + 1);
ll ans = v;
int i;
for (i = 2; 1ll * i * i <= v; i ++)
if (v % i == 0) {
if (isloop(i,p)) {
ans = i;
break;
}
}
while (i > 1) {
if (v % i == 0)
if (isloop(v / i, p)) {
ans = v / i;
break;
}
i --;
}
return ans;
}
ll lcm(ll x, ll y) {
return x / __gcd(x, y) * y;
}
ll get_loop(ll p) {
A.v[0][1] = 1;
A.v[1][1] = 1;
A.v[1][0] = 1;
ll ans = 1;
for (int i = 2; 1ll * i * i <= p;i ++)
if (p % i == 0) {
p /= i;
ll v = get_prime_loop(i);
while (p % i == 0) p /= i, v *= i;//, x *= i;
ans = lcm(ans, v);
}
if (p != 1) {
ans = lcm(ans, get_prime_loop(p));
}
return ans;
}
ll power_loop(ll x0, ll p){
vector<ll>d;
ll cur = p, next = p;
do {
next = get_loop(cur = next);
d.push_back(cur);
} while (next != cur);
ll x;
for (int i = 0; i < d.size(); i ++){
x = x0;
for (int j = i; j >= 0; j --) x = fib(x, d[j]);
if (x % p == x0 % p) return i + 1;
}
int v = d.size();
x = x0;
unordered_set<ll>vis;
while (vis.find(x) == vis.end()) {
vis.insert(x);
ll y = x;
for (int j = d.size() - 1; j >= 0; j --) y = fib(y, d[j]);
if (y % p == x0 % p) return v;
v ++;
x = fib(x, d[d.size() - 1]);
}
return -1;
}
}
int main(){
int T;
scanf("%d", & T);
while (T --) {
ll n, p;
scanf("%lld %lld", &n, &p);
printf("%d\n", Fibonacci_loop::power_loop(n, p));
}
return 0;
}