【C】指数取余

博主： Fivk
发布时间：2020 年 10 月 19 日
1554 次浏览
873字数
分类： C/C++

先来看两道题![题1](https://blog.fivk.cn/usr/uploads/2020/10/299198498.png)

---

![题2](https://blog.fivk.cn/usr/uploads/2020/10/1936999561.png)

---

1. 这里就不能直接算了
2. 没有任何数据可以储存
3. 所以我们需要定义一个算法

*发现一篇文章还挺好的*

`<div class="preview">
<div class="post-inser post box-shadow-wrap-normal">
<a href="https://blog.csdn.net/Harington/article/details/87602682?utm_source=app" target="_blank" class="post_inser_a no-external-link no-underline-link">

<div class="inner-content" style="margin-left: 10px;">
<p class="inser-title">快速幂</p>
<div class="inster-summary text-muted">
求 a^b % m的值
</div>
</div>
</a>

</div>

</div>`

对于上面的题有这些算法：

思路:  (a* b * c) % n ＝ ( ( ( a % n )  * b % n ) * c )%n

```
#include<stdio.h>
int main()
{
	int a,b;
	scanf("%d%d",&a,&b);
	int x=1;
	for(int i=1;i<=b;i++){
		x*=a;
		x=x%7;
	}
	printf("%d",x);
	return 0;
}
```

```
#include<stdio.h>
int main()
{
	int a=3,b=2000,ans=1,m=7;
	while(b>0)
	{
		if(b&1)
		{
			ans=ans*a%m;
		}
		a=a*a%m;
		b>>=1;
	}
	printf("%d",ans);
	return 0;
}
```

---

<div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-b8a3668d0354c38e80329fb893db764c6" aria-expanded="true"><div class="accordion-toggle"><span style="">题2，算法1</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-b8a3668d0354c38e80329fb893db764c6" class="collapse collapse-content"><p></p>思路就是余1000就剩下三位数了。

```
#include<stdio.h>
int main()
{
	int a,b;
	scanf("%d%d",&a,&b);
	int x=1;
	for(int i=1;i<=b;i++){
		x*=a;
		x=x%1000;
	}
	printf("%03d",x);
	return 0;
}

```

<p></p></div></div></div>
<div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-fafbc0c5e292b8ce4f47a13d5627624821" aria-expanded="true"><div class="accordion-toggle"><span style="">题2，算法2（一个大佬写的，看不懂）</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-fafbc0c5e292b8ce4f47a13d5627624821" class="collapse collapse-content"><p></p>

```
#include<iostream>
using namespace std;
int main()
{
	int a,b,k=1,i;
	cin>>a>>b;
	for(i=1;i<=b;i++)
	{
		k*=a;
		k%=1000;//k储存a^i的后三位 
	}
	if(k>=0)
	cout<<k<<endl;
	else if(k>=10)
		cout<<"0"<<k<<endl;//处理结果不为后3位的情况
		 else
		 cout<<"00"<<k<<endl;
		 return 0;

}
```

*这个现在还看不懂*

cin就是scanf，cout，就是printf

---

题目描述

输入整数m，n，k，求mn mod k的值。m，n，k*k为长整型范围内的自然数。
</div>

输入

输入一行3个整数，分别为m，n和k。
</div>

输出

输出一行一个整数，表示结果。
</div>

样例输入

复制样例数据

2 10 9

样例输出

7
</div>

![举例](http://shp.qpic.cn/collector/3253209438/8e9b53aa-7895-4392-aaa6-65787b6b719b/0)

```c
#include<bits/stdc++.h>
using namespace std;
typedef long int ll;
int main()
{
  ll m,n,k;
  cin>>m>>n>>k;
  ll res=1%k;
  while(n)
  {
    if(n&1) res=res*m%k;
    m=m*m%k;
    n>>=1;
  //  cout<<res<<endl;
  }
  cout<<res<<endl;
}

```

最后修改：2020 年 10 月 29 日

如果觉得我的文章对你有用，请随意赞赏

【C】指数取余

Fivk • 2020 年 10 月 19 日

先来看两道题![题1](https://blog.fivk.cn/usr/uploads/2020/10/299198498.png)

---

![题2](https://blog.fivk.cn/usr/uploads/2020/10/1936999561.png)

---

1. 这里就不能直接算了
2. 没有任何数据可以储存
3. 所以我们需要定义一个算法

*发现一篇文章还挺好的*

对于上面的题有这些算法：

思路:  (a* b * c) % n ＝ ( ( ( a % n )  * b % n ) * c )%n

```
#include<stdio.h>
int main()
{
	int a,b;
	scanf("%d%d",&a,&b);
	int x=1;
	for(int i=1;i<=b;i++){
		x*=a;
		x=x%7;
	}
	printf("%d",x);
	return 0;
}
```

```
#include<stdio.h>
int main()
{
	int a=3,b=2000,ans=1,m=7;
	while(b>0)
	{
		if(b&1)
		{
			ans=ans*a%m;
		}
		a=a*a%m;
		b>>=1;
	}
	printf("%d",ans);
	return 0;
}
```

---

```
#include<stdio.h>
int main()
{
	int a,b;
	scanf("%d%d",&a,&b);
	int x=1;
	for(int i=1;i<=b;i++){
		x*=a;
		x=x%1000;
	}
	printf("%03d",x);
	return 0;
}

```

}
```

*这个现在还看不懂*

cin就是scanf，cout，就是printf

---

题目描述

输入整数m，n，k，求mn mod k的值。m，n，k*k为长整型范围内的自然数。
</div>

输入

输入一行3个整数，分别为m，n和k。
</div>

输出

输出一行一个整数，表示结果。
</div>

样例输入

复制样例数据

2 10 9

样例输出

7
</div>

![举例](http://shp.qpic.cn/collector/3253209438/8e9b53aa-7895-4392-aaa6-65787b6b719b/0)

```

【C】指数取余

【踩坑日志】SpringBoot项目启动提示This primary key of "id" is primitive !不建议如此请使用包装类 in Class:

【C】极域电子教室学生端解除控制

【开发技巧】@CrossOrigin注解解决跨域问题

这是好东西

【Fivk】文章归档

【C】文件_字节读写函数（fgetc，fputc）

【C】动态内存的申请

【开发技巧】redis中的布隆过滤器

【C】指针和二维数组的一些问题

【算法基础】关于二分查找

【C】指数取余