数论专题小结：取模运算模板

1.大整数取模

（1）题意：输入正整数n,m，输出n mod m的值。n≤10^100,m≤10^9。

（2）思路：把大整数拆开，逐步取模。

#define N 1000+10
char n[N];
int m;
int main()
{
scanf("%s%d", n, &m);
int len = strlen(n);
int ans = 0;
for (int i = 0; i < len; i++)
ans = (int)(((long long)ans * 10 + n[i] - '0') % m);
printf("%dn", ans);
}

2.幂取模

（1）题意：输入正整数a,n,m，输出 a^n mod m 的值。a,n,m≤10^9。

（2）思路：利用分治法解决。

int pow_mod(int a, int n, int m)
{
if (n == 0)return 1;
int x = pow_mod(a, n / 2, m);
long
long ans = (long long)x*x%m;
if (n & 1)ans = ans*a%m;
return (int)ans;
}

大多数时候用如下代码更简洁

typedef long long LL;
LL pow_mod(LL x, LL n, LL mod)
{
LL ans = 1;
while (n > 0)
{
if (n & 1)ans = ans*x%mod;//如果二进制最低位是1，那么乘以x^(2^i)
x = x*x%mod;//将x平方
n >>= 1;
}
return ans;
}

（1）题意：输入正整数a,b,n,解方程 ax ≡ b (mod n) 。a,b,n≤10^9。

（2）思路：等价于求解 ax-ny=b。先求出g=gcd(a,n)，解方程 ax-ny=g得到一组解x0,y0。那么原方程解为x0*(b/g),y0*(b/g)。

void exgcd(int a, int b, int&d, int&x, int&y)
{
if (!b){ d = a, x = 1, y = 0; }
else
{
exgcd(b, a%b, d, y, x);
y -= x*(a / b);
}
}
int main()
{
int a, b, n;
cin >> a >> b >> n;
int g, x, y;
exgcd(a, n, g, x, y);
x *= (b / g);
printf("%dn", x);
}

最后

以上就是眼睛大朋友为你收集整理的数论专题小结：取模运算模板的全部内容，希望文章能够帮你解决数论专题小结：取模运算模板所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。