hdu 2837 Calculation 指数循环节套路题

时间:2022-08-25 10:48:25

Calculation

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2272    Accepted Submission(s): 536

Problem Description
Assume that f(0) = 1 and 0^0=1. f(n) = (n%10)^f(n/10) for all n bigger than zero. Please calculate f(n)%m. (2 ≤ n , m ≤ 10^9, x^y means the y th power of x).
 
Input
The first line contains a single positive integer T. which is the number of test cases. T lines follows.Each case consists of one line containing two positive integers n and m.
 
Output
One integer indicating the value of f(n)%m.
 
Sample Input
2
24 20
25 20
 
Sample Output
16
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 指数循环节套路题的更多相关文章

  1. HDU 4335 What is N&quest;(指数循环节)题解

    题意: 询问有多少数\(n\)满足\(n^{n!}\equiv b\mod p \land\ n\in[1,M]\),数据范围:\(M\leq2^{64}-1,p\leq1e5\) 思路: 这题显然要 ...

  2. hdu 5895 Mathematician QSC 指数循环节&plus;矩阵快速幂

    Mathematician QSC Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Othe ...

  3. hdu 3054 Fibonacci 找循环节的公式题

    Fibonacci Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others) Proble ...

  4. HDU2837 Calculation(指数循环节)题解

    题意: 已知\(f(0)=1,f(n)=(n\%10)^{f(n/10)}\),求\(f(n)\mod m\) 思路: 由扩展欧拉定理可知:当\(b>=m\)时,\(a^b\equiv a^{b ...

  5. hdu 2837 Calculation

    公式:a^b%p=a^(b%phi(p)+phi(p))%p   b>=phi(p) #include<iostream> #include<stdio.h> #incl ...

  6. 指数循环节 求A的B次方模C

    phi(c)为欧拉函数, 欧拉定理 : 对于互质的正整数 a 和 n ,有 aφ(n)  ≡ 1 mod n  . A^x = A^(x % Phi(C) + Phi(C)) (mod C) (x & ...

  7. 指数循环节&amp&semi;欧拉降幂

    证明:https://www.cnblogs.com/maijing/p/5046628.html 注意使用条件(B的范围) 例题: FZU1759 HDU2837 ZOJ1674 HDU4335

  8. HDU 5895 Mathematician QSC&lpar;矩阵乘法&plus;循环节降幂&plus;除法取模小技巧&plus;快速幂&rpar;

    传送门:HDU 5895 Mathematician QSC 这是一篇很好的题解,我想讲的他基本都讲了http://blog.csdn.net/queuelovestack/article/detai ...

  9. HDU 3746 Cyclic Nacklace &lpar;KMP求循环节问题&rpar;

    <题目链接> 题目大意: 给你一个字符串,要求将字符串的全部字符最少循环2次需要添加的字符数. [>>>kmp next函数 kmp的周期问题]  #include &l ...

随机推荐

  1. 移动开发viewport

    三种 viewport layout viewport:文档流的 css 宽度,是一个静态的值,使用 document.documentElement.clientWidth 获取,在meta中是 w ...

  2. 单位圆盘的全纯自同构群Aut B&lpar;0&comma;1&rpar;

    利用Schwarz引理可以求出单位圆盘$B(0,1)$的全纯自同构群${\rm Aut}B(0,1)$. 任取$a\in B(0,1)$,记$$\varphi_{a}(z)=\frac{a-z}{1- ...

  3. 如何消除移动端a标签点击时的蓝色底色以及a标签link、visited、hover、active的顺序

    1.消除a标签移动端点击时的蓝色底色 -webkit-tap-highlight-color:transparent 2.link.visited.hover.active的顺序 a:link{tex ...

  4. percona-toolkit 之 【pt-deadlock-logger】说明

    摘要: 死锁:是指两个或则多个事务在同一个资源上相互占用,并请求锁定对方占用的资源,而导致恶性循环的现象:当产生死锁的时候,MySQL会回滚一个小事务的SQL,确保另一个完成.上面是死锁的概念,而在M ...

  5. 类:String,Math,DateTime,Random随机数,异常保护

    String类: 练习: Math类: Random随机数: DateTime类: 异常保护: 练习: 1. 2. 3.方法一: 方法二: 4.人机大战石头剪刀布 5. //请输入你想输入的数字 // ...

  6. HDU1250:Hat&&num;39&semi;s Fibonacci

    Problem Description A Fibonacci sequence is calculated by adding the previous two members the sequen ...

  7. eclipse hibernate插件在线安装

    下面介绍下 关于在eclipse下如何在线安装插件 首先需要打开eclipse  点击 安装完成后,进入hibernate视图,在左侧窗口右键add configuration, 第一个name属性, ...

  8. &lbrack;PY3&rsqb;——Queue

    Queue class Queue(builtins.object) __init__(self, maxsize=0) empty(self) full(self) get(self, block= ...

  9. &lbrack;leetcode&rsqb;Copy List with Random Pointer &commat; Python

    原题地址:https://oj.leetcode.com/problems/copy-list-with-random-pointer/ 题意: A linked list is given such ...

  10. 022&lowbar;Hadoop中的数据类型(Writable、WritableComparable、Comparator、RawComparator…)

    1. 在hadoop中所有的key/value都必须实现Writable接口,有两个方法,分别用于读(反序列化)和写(序列化)操作.