Calculation
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2272 Accepted Submission(s): 536
24 20
25 20
5
题意:求解$f(n) = {(n\%10)}^{f(n/10)}\%m $,其中$(2 <= n, m <= 10^9)$;
思路:一看到指数模除,并且没有说明是否互素,直接上指数循环节,化简指数==套路...
注:
1. 使用指数循环节都是递归形式,所以欧拉函数也需要是递归形式;
2. 在指数循环节中的快速幂时,需要在ans >= mod时,模完之后还要加上mod;
#include <iostream>
#include<cstdio>
using namespace std;
#define ll long long
ll phi(ll c)
{
ll ans = c;
for(int i = ; i*i <= c; i++) {
if(c%i == ){
ans -= ans/i;
while(c%i == ) c /= i;
}
}
if(c > ) ans -= ans/c;
return ans;
}
ll quick_mod(ll a, ll b, ll mod)
{
if(a >= mod) a = a%mod + mod; // 并不是直接%mod
ll ans = ;
while(b){
if(b&){
ans = ans*a;
if(ans >= mod) ans = ans%mod + mod; //**
}
a *= a;
if(a >= mod) a = a%mod + mod; //**
b >>= ;
}
return ans;
}
ll solve(ll n, ll m)
{
ll p = phi(m);
if(n == ) return ;
ll index = solve(n/, p); return quick_mod(n%, index, m);
}
int main()
{
ll n, m, T;
cin >> T;
while(T--){
scanf("%I64d%I64d", &n, &m);
printf("%I64d\n", solve(n,m)%m);
}
return ;
}
hdu 2837 Calculation 指数循环节套路题的更多相关文章
-
HDU 4335 What is N?(指数循环节)题解
题意: 询问有多少数\(n\)满足\(n^{n!}\equiv b\mod p \land\ n\in[1,M]\),数据范围:\(M\leq2^{64}-1,p\leq1e5\) 思路: 这题显然要 ...
-
hdu 5895 Mathematician QSC 指数循环节+矩阵快速幂
Mathematician QSC Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Othe ...
-
hdu 3054 Fibonacci 找循环节的公式题
Fibonacci Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others) Proble ...
-
HDU2837 Calculation(指数循环节)题解
题意: 已知\(f(0)=1,f(n)=(n\%10)^{f(n/10)}\),求\(f(n)\mod m\) 思路: 由扩展欧拉定理可知:当\(b>=m\)时,\(a^b\equiv a^{b ...
-
hdu 2837 Calculation
公式:a^b%p=a^(b%phi(p)+phi(p))%p b>=phi(p) #include<iostream> #include<stdio.h> #incl ...
-
指数循环节 求A的B次方模C
phi(c)为欧拉函数, 欧拉定理 : 对于互质的正整数 a 和 n ,有 aφ(n) ≡ 1 mod n . A^x = A^(x % Phi(C) + Phi(C)) (mod C) (x & ...
-
指数循环节&;欧拉降幂
证明:https://www.cnblogs.com/maijing/p/5046628.html 注意使用条件(B的范围) 例题: FZU1759 HDU2837 ZOJ1674 HDU4335
-
HDU 5895 Mathematician QSC(矩阵乘法+循环节降幂+除法取模小技巧+快速幂)
传送门:HDU 5895 Mathematician QSC 这是一篇很好的题解,我想讲的他基本都讲了http://blog.csdn.net/queuelovestack/article/detai ...
-
HDU 3746 Cyclic Nacklace (KMP求循环节问题)
<题目链接> 题目大意: 给你一个字符串,要求将字符串的全部字符最少循环2次需要添加的字符数. [>>>kmp next函数 kmp的周期问题] #include &l ...
随机推荐
-
移动开发viewport
三种 viewport layout viewport:文档流的 css 宽度,是一个静态的值,使用 document.documentElement.clientWidth 获取,在meta中是 w ...
-
单位圆盘的全纯自同构群Aut B(0,1)
利用Schwarz引理可以求出单位圆盘$B(0,1)$的全纯自同构群${\rm Aut}B(0,1)$. 任取$a\in B(0,1)$,记$$\varphi_{a}(z)=\frac{a-z}{1- ...
-
如何消除移动端a标签点击时的蓝色底色以及a标签link、visited、hover、active的顺序
1.消除a标签移动端点击时的蓝色底色 -webkit-tap-highlight-color:transparent 2.link.visited.hover.active的顺序 a:link{tex ...
-
percona-toolkit 之 【pt-deadlock-logger】说明
摘要: 死锁:是指两个或则多个事务在同一个资源上相互占用,并请求锁定对方占用的资源,而导致恶性循环的现象:当产生死锁的时候,MySQL会回滚一个小事务的SQL,确保另一个完成.上面是死锁的概念,而在M ...
-
类:String,Math,DateTime,Random随机数,异常保护
String类: 练习: Math类: Random随机数: DateTime类: 异常保护: 练习: 1. 2. 3.方法一: 方法二: 4.人机大战石头剪刀布 5. //请输入你想输入的数字 // ...
-
HDU1250:Hat&#39;s Fibonacci
Problem Description A Fibonacci sequence is calculated by adding the previous two members the sequen ...
-
eclipse hibernate插件在线安装
下面介绍下 关于在eclipse下如何在线安装插件 首先需要打开eclipse 点击 安装完成后,进入hibernate视图,在左侧窗口右键add configuration, 第一个name属性, ...
-
[PY3]——Queue
Queue class Queue(builtins.object) __init__(self, maxsize=0) empty(self) full(self) get(self, block= ...
-
[leetcode]Copy List with Random Pointer @ Python
原题地址:https://oj.leetcode.com/problems/copy-list-with-random-pointer/ 题意: A linked list is given such ...
-
022_Hadoop中的数据类型(Writable、WritableComparable、Comparator、RawComparator…)
1. 在hadoop中所有的key/value都必须实现Writable接口,有两个方法,分别用于读(反序列化)和写(序列化)操作.