专栏文章

题解：P13762 Extended Fibonacci

IICU_midway_azuma
P13762题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio9im7m
此快照首次捕获于
2025/12/02 15:34
3 个月前
此快照最后确认于
2025/12/02 15:34
3 个月前
查看原文
首先将每个数  mod 2\bmod 2，得到如下一个序列：110110110110⋯1 1 0110110110\cdots。
答案只与 p mod 3 p\bmod 3 和 q mod 3q\bmod3 的值有关是非常显然的。
直接枚举 pp 和 q mod 3q\bmod3 的值，然后我们可以将整个序列看成如下形式：
10110⋯11011\color{0000FF}\text{10}\color{000000}\text{110}\cdots110\color{FF0000}\text{11}；
也就是说，蓝色部分为头部，红色部分为尾部，整个序列由头部、尾部这两个不完整的循环以及中间的完整循环构成。
设中间有 xx 个循环，那么可以根据不同的起止点位置列出不同的一元二次方程，任意一种情况有整数解即可。
一元二次方程推导过程详见代码注释（可以看到代码非常长，因为有很多注释和重复部分，实际上可以压缩到四五十行左右）。
数据范围 a≤1017a\leq 10^{17} 而非通常的 101810^{18} 为刻意设置，保证暴力计算 Δ\Delta 时不会爆 long long。
有更简洁的做法，但自认为代码更好理解。
CPP
#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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...