AT_abc446_e [ABC446E] Multiple-Free Sequences
题目描述
Among integer pairs $ (x, y) $ satisfying $ 0 \\leq x,y \\leq M-1 $ , how many are there such that the infinite sequence $ (s_1, s_2, \\dots) $ defined by the following recurrence relation contains no multiples of $ M $ ?
- $ s_1 = x $
- $ s_2 = y $
- $ s_n = A s_{n-1} + B s_{n-2} $ ( $ n \\geq 3 $ )
输入格式
The input is given from Standard Input in the following format:
$ M $ $ A $ $ B $
输出格式
Output the answer on one line.
输入输出样例 #1
输入 #1
4 1 2
输出 #1
7
输入输出样例 #2
输入 #2
446 1 1
输出 #2
0
输入输出样例 #3
输入 #3
1000 784 385
输出 #3
995373
说明/提示
Sample Explanation 1
The integer pairs satisfying the condition in the problem statement are $ (x,y) = (1,1), (1,3), (2,1), (2,2), (2,3), (3,1), (3,3) $ , for a total of seven pairs.
For example, when $ (x,y) = (2,1) $ , the corresponding sequence is $ (2,1,5,7,17,31,65,127,\\dots) $ . This sequence contains no multiples of $ 4 $ . Thus, $ (x,y) = (2,1) $ satisfies the condition in the problem statement.
On the other hand, when $ (x,y) = (3,2) $ , the corresponding sequence is $ (3,2,8,12,28,52,108,212,\\dots) $ . The third term of this sequence is $ 8 $ , which is a multiple of $ 4 $ . Thus, $ (x,y) = (3,2) $ does not satisfy the condition in the problem statement.
Sample Explanation 2
No integer pairs satisfy the condition in the problem statement.
Constraints
- $ 2 \\leq M \\leq 1000 $
- $ 0 \\leq A, B \\leq M-1 $
- All input values are integers.
思路
MAP，直接AC。
代码见下
using namespace std;
long long m,a,b,s[100005],d=0,bo=0,op=0,os=100000;
unordered_map<long long,int> mp;
unordered_map<long long,int> mps;
int main(){
cin>>m>>a>>b;
//if(a==1&&b==1){
//cout<<0<<endl;
//return 0;
//}
for(int i=1;i<=m-1;i++){
for(int j=1;j<=m-1;j++){
d=2;
s[1]=i;
s[2]=j;
mp.clear();
if(mps[i*os+j]==2){
op++;
continue;
}
if(mps[i*os+j]==1){
continue;
}
mp[i*os+j]=1;
bo=0;
for(int k=3;;k++){
s[k]=(a*s[k-1]+b*s[k-2])%m;
if(s[k]==0){
bo=1;
for(int o=2;o<=k;o++){
mps[s[o-1]*os+s[o]]=1;
}
bo=1;
break;
}
if(mps[s[k-1]*os+s[k]]==1){
for(int o=2;o<=k;o++){
mps[s[o-1]*os+s[o]]=1;
}
bo=1;
break;
}
if(mps[s[k-1]*os+s[k]]==2){
for(int o=2;o<=k;o++){
mps[s[o-1]*os+s[o]]=2;
}
bo=0;
break;
}
if(mp[s[k-1]*os+s[k]]==1){
if(bo==1){
for(int o=2;o<=k;o++){
mps[s[o-1]*os+s[o]]=1;
}
bo=1;
}
else{
for(int o=2;o<=k;o++){
mps[s[o-1]*os+s[o]]=2;
}
bo=0;
}
break;
}
mp[s[k-1]*os+s[k]]=1;
}
if(bo==0){
op++;
}
}
}
cout<<op<<endl;
return 0;
}
