题解：P16345 阿瓦的数列
Code_to_Win
·
·
题解
题解：阿瓦的数列
一道大水题，其实我也调了好久。
思路
这不是很明显的一个递归吗。 是递归就有递归式，本题的递推式也是题目给你的：
本以为直接递推就行了，注意要特判：
### [TLE](https://www.luogu.com.cn/record/275169439) Code：
```
#include<bits/stdc++.h>
#define int long long
using namespace std;
void arr(){
int x,y,n; cin>>x>>y>>n;
int z=0;
if(n==1){
cout<<x<<endl; return ;
}
if(n==2){
cout<<y<<endl; return ;
}
for(int i=3;i<=n;i++){
z=(x%i)*(y%i)%i;
x=y; y=z;
}
cout<<y<<endl;
}
signed main(){
int t; cin>>t;
while(t--){
arr();
}
return 0;
}
```
暴力只得到了少少的 40 分，看来要考虑优化。
我们发现从第 3 个数开始就要将 $f_i \bmod i$，所以 $f_3$ 的取值只能是 $[0,2]$ 中的整数，$f_4$ 的取值只能是 $[0,3]$ 中的整数。
通过 $f_3$，$f_4$ 枚举发现，$f_{29}<2$，$f_{30}<2$，也就是说当 $i>28$ 时 $f_i<2$。
如果 $n<29$ 直接暴力递推就行了，否则分别讨论 $f_{29}$，$f_{30}$ 是否为 0 就行了。
十年 OI 一场空，不开 long long 见祖宗！
### [AC]() Code
```
#include<bits/stdc++.h>
#define int long long
using namespace std;
void arr(){
int x,y,n; cin>>x>>y>>n;
if(n==1){
cout<<x<<endl; return ;
}
if(n==2){
cout<<y<<endl; return ;
}
int z;
for(int i=3;i<=n;i++){
z=(x%i)*(y%i)%i;
if(z==0){
cout<<0<<endl; return ;
}
if(y==1 and z==1){
cout<<1<<endl; return ;
}
x=y; y=z;
}
cout<<y<<endl;
}
signed main(){
int t; cin>>t;
while(t--){
arr();
}
return 0;
}
```
题解来之不易，点个赞再走吧……