学习建站的网站,珠海营销型网站,vr全景网站开发制作,wordpress 打不开题目链接
分析
首先这题给了很大的提示信息 注意 m 和 p 的范围 , 很自然的想到可以先把所有可能的 f ( x ) f(x) f(x) 算出来.
思维误区
有些人在算完 f ( x ) f(x) f(x) 之后可能就会去思考找环的问题#xff0c;然后一些码力弱的大佬就会祭掉.
在经过仔细的观察之后…题目链接
分析
首先这题给了很大的提示信息 注意 m 和 p 的范围 , 很自然的想到可以先把所有可能的 f ( x ) f(x) f(x) 算出来.
思维误区
有些人在算完 f ( x ) f(x) f(x) 之后可能就会去思考找环的问题然后一些码力弱的大佬就会祭掉.
在经过仔细的观察之后 (大多数人其实一眼就看出来了罢 , 可以发现最终答案的计算是符合结合律的或者说具有传递性 所以考虑倍增.
令 f a [ i ] [ j ] fa[i][j] fa[i][j] 表示 f 1 j ( i ) f_{1j}(i) f1j(i) 的值初始时把 f [ i ] [ 0 ] f[i][0] f[i][0] 算出来后面就可以直接倍增了.
Code
#include bits/stdc.h
#define int long long
const int N 1e510;using namespace std;
int m,q,p;
int ksm(int a, int b){int ans 1;while(b){if(b1){ans ans * a % p;}a a*a%p;b 1;}return ans;
}
int a[30],b[30];
int f[N];
int get(int x){int ans 0;for(int i 1; i m; i){ans (ans a[i]*ksm(x,b[i])%p) % p;}return ans;
}
bool vis[N];
int belong[N];
vectorint e[N];
int fa[N][30];
void init(){for(int i 0; i p; i){fa[i][0] get(i);}for(int i 1;i 25; i){for(int j 0; j p; j){fa[j][i] fa[fa[j][i-1]][i-1];}}
}
signed main(){cin m q p;for(int i 1; i m; i){cin a[i] b[i];a[i] % p;} init();while(q--){int x,y;cin x y;x % p;for(int i 25; i 0; i--){if((1 i) y) x fa[x][i],y - (1i);}cout x endl;}return 0;
}
