Exponial~(欧拉函数)~(发呆题)
Description
Everybody loves big numbers (if you do not, you might want to stop reading at this point). There are many ways of constructing really big numbers known to humankind, for instance:
- Exponentiation: 422016=42⋅42⋅...⋅422016 times422016=42⋅42⋅...⋅42⏟2016 times.
- Factorials: 2016!=2016 ⋅ 2015 ⋅ ... ⋅ 2 ⋅ 1.
In this problem we look at their lesser-known love-child the exponial, which is an operation defined for all positive integers n as
exponial(n)=n(n − 1)(n − 2)⋯21
For example, exponial(1)=1 and exponial(5)=54321 ≈ 6.206 ⋅ 10183230 which is already pretty big. Note that exponentiation is right-associative: abc = a(bc).
Since the exponials are really big, they can be a bit unwieldy to work with. Therefore we would like you to write a program which computesexponial(n) mod m (the remainder of exponial(n) when dividing by m).
Input
There will be several test cases. For the each case, the input consists of two integers n (1 ≤ n ≤ 109) and m (1 ≤ m ≤ 109).
Output
Output a single integer, the value of exponial(n) mod m.
Sample Input
2 42
5 123456789
94 265
Sample Output
2
16317634
39
Hint
Source
NCPC 2016
这题题意很容易懂 但是数学不好,只能看看。
在没做这题之前我都不知道有欧拉函数这个东西
AB mod C=AB mod φ(C)+φ(C) mod C(B>φ(C))
φ(C)表示小于等于C和C互质的数目。
此处只是提供一个模板,等我对欧拉函数了解后,
我会写一篇详细的关于欧拉函数的详解。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
const int maxn =1e5+;
typedef long long ll;
ll n,m,ans;
ll euler(ll n)
{
ll res=n,a=n;
for (ll i= ;i*i <=a ;i++ ){
if (a%i==) {
res=res/i*(i-);
while(a%i==) a/=i;
}
}
if (a>) res=res/a*(a-);
return res;
}
ll modexp(ll a,ll b,ll c)
{
ll res=;
while(b){
if (b&) res=res*a%c;
a=a*a%c;
b=b>>;
}
return res;
}
ll getans(ll n,ll m )
{
if (m==) return ;
if (n==) return ;
else if (n==) return %m;
else if (n==) return %m;
else if (n==) return modexp(,,m);
else {
ll phi=euler(m);
ll z=getans(n-,phi);
ans=modexp(n,phi+z,m);
}
return ans;
}
int main() {
while(scanf("%lld%lld",&n,&m)!=EOF){
printf("%lld\n",getans(n,m));
}
return ;
}
最新文章
- O2O的实时搜索引擎
- C#------EntityFramework实体加载数据库SQLServer(MySQL)
- 【BZOJ】3093: [Fdu校赛2012] A Famous Game
- IOS之Foundation之探究学习Swift实用基础整理<;一>;
- CS6破解
- 【转】 SIFT算法详解
- js 触摸类库
- [XML] C#ResourceManagerWrapper帮助类 (转载)
- phpmailer邮件类下载(转)
- JavaScript---while和do while的区别
- 从头开始学JavaScript (十二)——Array类型
- 转: web 页面加载速度优化实战-100% 的飞跃提升
- Shopt命令(删除排除)
- Docker 系列六(Docker Swarm 项目).
- HDU/HDOJ 4864 Task
- .net导出excle无需任何插件,直接通过一个tablehtml实现
- 解决Maven管理项目update Maven时,jre自动变为1.5
- 基于鸢尾花数据的PCA降维处理
- php分享十八七:mysql基础
- effective c++读书笔记(一)