27 条题解
-
0
#include <bits/stdc++.h> using namespace std; #define int __int128 int read() { int x{},w{1};char c= getchar(); while(c>'9' || c<'0') {if(c == '-') w=-1;c = getchar();} while(c<='9' && c>='0') x = (x<<1)+(x<<3)+c-'0',c = getchar(); return w * x; } void write(int x) { if(x < 0) x = -x,putchar('-'); if(x>9) write(x/10);putchar(x%10+'0'); } void writeln(int x) { write(x);putchar(10); } const int N = 5e5+5; int f[N],d[N]; int siz[N],son[N]; struct EDGE { int nxt,to; }e[N<<1]; int ecnt{},head[N]; void add(int u,int v) { e[++ecnt].to = v; e[ecnt].nxt = head[u]; head[u] = ecnt; } void dfs1(int u,int fa) { siz[u] = 1,f[u] = fa,d[u] = d[fa]+1; for(int i{head[u]};i;i = e[i].nxt) { int v = e[i].to; if(v == fa) continue; dfs1(v,u); siz[u] += siz[v]; if(siz[v] > siz[son[u]]) son[u] = v; } } int t[N],dfn[N],a[N],o[N],cnt{}; void dfs2(int u,int top) { dfn[u] = ++cnt; a[dfn[u]]=o[u]; t[u] = top; if(!son[u]) return; dfs2(son[u],top); for(int i{head[u]};i;i = e[i].nxt) { int v = e[i].to; if(v == f[u] || v == son[u]) continue; dfs2(v,v); } } int lca(int u,int v) { while(t[u] != t[v]) { if(d[t[u]] < d[t[v]]) u^=v^=u^=v; u = f[t[u]]; } return d[u]<d[v] ? u : v; } int qp(int a,int b,int p) { int res{1}; while(b) { if(b & 1) res = res * a % p; a = a * a % p; b >>= 1; } return res; } signed main() { int a = read(),b = read(),p = read(); writeln(qp(a,b,p)); }
信息
- ID
- 171
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 2
- 标签
- 递交数
- 1165
- 已通过
- 373
- 上传者