acm数论题目 a^b^c mod 1000000007 如何快速幂.数据范围三个数都小于 1000000000.
来源:学生作业帮 编辑:神马作文网作业帮 分类:数学作业 时间:2024/09/30 06:22:36
acm数论题目 a^b^c mod 1000000007 如何快速幂.数据范围三个数都小于 1000000000.
#include
typedef __int64 lld;
lld mod(lld a,lld b,lld m)
{
\x05lld ret=1;
\x05a%=m;
\x05while(b)
\x05{
\x05\x05if(b&1)ret=ret*a%m;
\x05\x05b>>=1;
\x05\x05a=a*a%m;
\x05\x05//printf("b=%I64d\n",b);
\x05}
\x05return ret;
}
int main()
{
\x05lld a,b,c;
\x05lld m = 1000000007;
\x05while(scanf("%I64d%I64d%I64d",&a,&b,&c)!=EOF)
\x05{
\x05\x05b=mod(b,c,m-1);//应该用费马小定理,把b^c先降下来
\x05\x05a=mod(a,b,m);
\x05\x05printf("%I64d\n",a);
\x05}
\x05return 0;
}
再问: 大侠 ,费马小定理 能否稍微解释一下。
再答: 恩,就是欧拉函数知道吗? 1000000007是一个素数 如果(a,b)=1 那么 a^c%b=a^(c%(phi(b)))%b phi(b) 是指b的欧拉函数,就是比b小的数字中有多少个数和b的公因子是1。 素数的欧拉函数是自身减一。其他的你自己去具体看看一下相关知道吧
typedef __int64 lld;
lld mod(lld a,lld b,lld m)
{
\x05lld ret=1;
\x05a%=m;
\x05while(b)
\x05{
\x05\x05if(b&1)ret=ret*a%m;
\x05\x05b>>=1;
\x05\x05a=a*a%m;
\x05\x05//printf("b=%I64d\n",b);
\x05}
\x05return ret;
}
int main()
{
\x05lld a,b,c;
\x05lld m = 1000000007;
\x05while(scanf("%I64d%I64d%I64d",&a,&b,&c)!=EOF)
\x05{
\x05\x05b=mod(b,c,m-1);//应该用费马小定理,把b^c先降下来
\x05\x05a=mod(a,b,m);
\x05\x05printf("%I64d\n",a);
\x05}
\x05return 0;
}
再问: 大侠 ,费马小定理 能否稍微解释一下。
再答: 恩,就是欧拉函数知道吗? 1000000007是一个素数 如果(a,b)=1 那么 a^c%b=a^(c%(phi(b)))%b phi(b) 是指b的欧拉函数,就是比b小的数字中有多少个数和b的公因子是1。 素数的欧拉函数是自身减一。其他的你自己去具体看看一下相关知道吧
acm数论题目 a^b^c mod 1000000007 如何快速幂.数据范围三个数都小于 1000000000.
acm题目的a+b用c语言怎么写
A.B.C三个数相加等于22、A.b.c三个数相乘等于B的55倍.A小于B小于C,问B是多少?
a 、b 、c三个数都不等于零,当b
a*七分之三=b*五分之四=c*四分之三,并且a,b,c都不为零,把这三个数按照重小到大排列是()小于()小于()
将a又3分之2,b又6分之5,C又8分之7,分分数后,三个分数的分子恰好相同.已知a.b.c都小于10,求a.b.c.
若三个数的和小于零则() a.三个数中至少有两个负数 b.三个数中有且只有一个负数 c.三个数中
三个数a,b,c成等比数列,且a+b+c=m,求b的取值范围
c程序acm题目A+B for Input-Output Practice (VII) Time Limit : 200
excel调整列顺序:例如,一个表中有A B C D 四列,如何快速将数据调整为D C B A 排列
=4,b=3,c=2,d=1下列表达式的值是a大于b+1 or c小于d and b mod c
已知A B C三个数用数轴B小于A A小于0 C大于0,化简A加B的绝对值,减B加C的绝对值,加A减C的绝对值