NYOJ102. 次方求模（数论——模运算+快速幂运算）

2019-04-14 20:24发布

站内文章 / 模拟电子
15186 0 1510

次方求模

时间限制：1000 ms  |  内存限制：65535 KB 难度：3
描述
求a的b次方对c取余的值
输入
第一行输入一个整数n表示测试数据的组数（n<100）
每组测试只有一行，其中有三个正整数a,b,c(1=
输出
输出a的b次方对c取余之后的结果
样例输入
3 2 3 5 3 100 10 11 12345 12345
样例输出
3 1 10481

【分析】数论——模运算+快速幂运算 #include typedef long long ll; ll n; ll a,b,c; ll pw(ll a,ll b,ll c) { ll res=1; if(b==0) return 1; res=pw(a*a%c,b/2,c); if(b&1) res=res*a%c; return res; } int main() { ll res; scanf("%lld",&n); while(n--) { scanf("%lld %lld %lld",&a,&b,&c); a%=c; res=pw(a,b,c); printf("%lld ",res); } return 0; }

热门文章