题解：P13762 Extended Fibonacci
ICU_midway_azuma
·
·
题解
首先将每个数 \bmod 2，得到如下一个序列：1 1 0110110110\cdots。
答案只与 p\bmod 3 和 q\bmod3 的值有关是非常显然的。
直接枚举 p 和 q\bmod3 的值，然后我们可以将整个序列看成如下形式：
也就是说，蓝色部分为头部，红色部分为尾部，整个序列由头部、尾部这两个不完整的循环以及中间的完整循环构成。
设中间有 $x$ 个循环，那么可以根据不同的起止点位置列出不同的一元二次方程，任意一种情况有整数解即可。
一元二次方程推导过程详见代码注释（可以看到代码非常长，因为有很多注释和重复部分，实际上可以压缩到四五十行左右）。
数据范围 $a\leq 10^{17}$ 而非通常的 $10^{18}$ 为刻意设置，保证暴力计算 $\Delta$ 时不会爆 `long long`。
有更简洁的做法，但自认为代码更好理解。
```
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
// long long A;
long long a;
cin>>a;
if(a==0){
cout<<"1 1\n";
continue;
}
bool fl=0;
long long ans1=0,ans2=0;
//
for(int i=0;i<=2;i++){
if(fl)break;
for(int j=0;j<=2;j++){
if(i==0){
if(j==0){
//j=i+3x
//a=(1+2+...+x)+(0+1+...+2x-1)
//a=(x+1)*x/2+(2x-1)*x
//(5/2)*x^2-(1/2)*x-a=0
//Δ= (40a+1)/4
if((long long)sqrt(40*a+1)*(long long)sqrt(40*a+1)==40*a+1&&(long long)(sqrt(40*a+1)+1)%10==0){
ans1=i+3;
ans2=i+3+3*((long long)(sqrt(40*a+1)+1)/2/5);
fl=1;
break;
}
}
else if(j==1){
//j=i+3x+1
//a=(1+2+...+x)+(0+1+...+2x)
//a=(x+1)*x/2+x*(2x+1)
//(5/2)*x^2+(3/2)x-a=0;
//Δ=(40a+9)/4
if((long long)sqrt(40*a+9)*(long long)sqrt(40*a+9)==40*a+9&&(long long)(sqrt(40*a+9)-3)%10==0){
ans1=i+3;
ans2=i+3+3*((long long)(sqrt(40*a+9)-3)/2/5)+1;
fl=1;
break;
}
}
else{
//j=i+3x+2;
//a=(1+2+...+x)+(0+1+...+2x+1)
//a=(x+1)*x/2+(2x+1)*(x+1)
//(5/2)*x^2+(7/2)*x+1-a=0;
//Δ=(40a+9)/4
// cout<<(int)(40*a+9)<<" "<<(int)sqrt(40*a+9)<<endl;
if((long long)sqrt(40*a+9)*(long long)sqrt(40*a+9)==40*a+9&&(long long)(sqrt(40*a+9)-7)%10==0){
ans1=i+3;
ans2=i+3+3*((long long)(sqrt(40*a+9)-7)/2/5)+2;
fl=1;
break;
}
}
}
else if(i==1){
if(j==1){
//j=i+3x
//a=(1+2+...+x-1)+(0+...+2x)
//a=x*(x-1)/2+x*(2x+1)
//(5/2)*x^2+(1/2)*x-a=0;
if((long long)sqrt(40*a+1)*(long long)sqrt(40*a+1)==40*a+1&&(int)(sqrt(40*a+1)-1)%10==0){
ans1=i+3;
ans2=i+3+3*((long long)(sqrt(40*a+1)-1)/2/5);
fl=1;
break;
}
}
else if(j==2){
//j=i+3x+1
//a=(1+2+...+x-1)+(0+1+...+2x+1)
//a=x*(x-1)/2+(2x+1)*(x+1)
//(5/2)*x^2+(5/2)*x+1-a=0;
//Δ=(40a-15)/4
if((long long)sqrt(40*a-15)*(long long)sqrt(40*a-15)==40*a-15&&(long long)(sqrt(40*a-15)-5)%10==0){
ans1=i+3;
ans2=i+3+3*((long long)(sqrt(40*a-15)-5)/2/5)+1;
fl=1;
break;
}
}
else{
//j=i+3x+2
//a=(1+2+...+x)+(0+1+...+2x+1)
//a=x*(x+1)/2+(2x+1)*(x+1)
//(5/2)*x^2+(7/2)*x+1-a=0;
//同i=0 j=2
if((long long)sqrt(40*a+9)*(long long)sqrt(40*a+9)==40*a+9&&(long long)(sqrt(40*a+9)-7)%10==0){
ans1=i+3;
ans2=i+3+3*((long long)(sqrt(40*a+9)-7)/2/5)+2;
fl=1;
break;
}
}
}
else{
if(j==2){
//j=i+3x
//a=(1+2+...+x-1)+(0+1+...+2x)
//同i=1 j=1
if((long long)sqrt(40*a+1)*(long long)sqrt(40*a+1)==40*a+1&&((long long)sqrt(40*a+1)-1)%10==0){
ans1=i+3;
ans2=i+3+3*((long long)(sqrt(40*a+1)-1)/2/5);
fl=1;
break;
}
}
else if(j==0){
//j=i+3x+1
//a=(1+2+...+x)+(0+1+...+2x)
//同i=0 j=1
if((long long)sqrt(40*a+9)*(long long)sqrt(40*a+9)==40*a+9&&((long long)sqrt(40*a+9)-3)%10==0){
ans1=i+3;
ans2=i+3+3*((long long)(sqrt(40*a+9)-3)/2/5)+1;
fl=1;
break;
}
}
else{
//j=i+3x+2
//a=(1+2+...+x)+(0+1+...+2x+1)
//同i=0 j=2
if((long long)sqrt(40*a+9)*(long long)sqrt(40*a+9)==40*a+9&&((long long)sqrt(40*a+9)-7)%10==0){
ans1=i+3;
ans2=i+3+3*(((long long)sqrt(40*a+9)-7)/2/5)+2;
fl=1;
break;
}
}
}
}
}
if(fl)cout<<ans1<<" "<<ans2<<"\n";
else cout<<"-1\n";
}
return 0;
}
//1 1 0 1 1 0 1 1 0 1 1 0x=2
```