HDU - 4704 - Sum 【费马小定理 + 快速幂】题解

川长思鸟来 2021-07-24 20:25 340阅读 0赞

### 目录 ###

*   *   *  1.题目
         *  2.代码

### 1.题目 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]  
**Input**  
2  
**Output**  
2

**Hint**

1.  For N = 2, S(1) = S(2) = 1.
2.  The input file consists of multiple test cases.

**Sample Input**  
2  
**Sample Output**  
2

### 2.代码 ###

#include<iostream>
    #include <stdio.h>
    using namespace std;
    char N[100005];
    const int mod=1e9+7;
    //费马小定理
    long long PhiMa(char *N,int mod)
    { 
        long long ans=0;
        for(int i=0;N[i]!='\0';i++)
            ans=(ans*10+N[i]-'0')%mod;
        return ans;
    }
    //快速幂取余运算
    long long FastPow(long long a,long long b)
    { 
       long long ans=1;
       while(b)
       { 
           if(b&1)
             ans=ans*a%mod;
           a=a*a%mod;
           b>>=1;
       }
       return ans;
    }
    int main()
    { 
        while(scanf("%s",N)!=EOF)
        { 
            long long n=PhiMa(N,mod-1)-1;
            printf("%d\n",FastPow(2,n));
        }
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/39360beccb84470c903775cc6d75539f.png

发表评论取消回复

表情：

评论列表（有 0 条评论，340人围观）

还没有评论，来说两句吧...

相关阅读

相关费马小定理【模板例题】

> 费马小定理： > 如果p是一个质数，而整数a不是p的倍数， > 则有a（p-1）≡1（mod p）。 > 即：假如a是整数，p是质数，且a,p互质(即两者只有一

蔚落/ 2022年12月10日 15:56/ 0 赞/ 199 阅读

相关欧拉函数和费马小定理（基础题题解）

太久没有在blog上记录学习进度啦，需要认真反思一下，陈老师的话如同醍醐灌顶，复习知识唤醒记忆，拥有一个属于自己的blog是一件引以为豪的事情，希望自己做的越来越好吧！加油！

Bertha 。/ 2022年09月29日 05:21/ 0 赞/ 179 阅读

相关费马小定理

费马小定理是 [数论][Link 1]中的一个重要定理，其内容为：假如p是 [质数][Link 2]，且(a,p)=1，那么 a^(p-1) ≡1（mod p

朱雀/ 2022年09月20日 15:29/ 0 赞/ 240 阅读

相关费马小定理与欧拉定理原理与证明

一、欧拉定理 1、定义若a与n互质，则 a φ ( n ) ≡ 1 a^\{\\varphi (n)\} \\equiv 1 aφ(n)≡1 (mod n)。

悠悠/ 2022年09月04日 15:53/ 0 赞/ 169 阅读

相关 C~K的难题——费马小定理

Think: 1快速幂 2费马小定理推论 [建议参考博客链接][Link 1] C~K的难题 Time Limit: 1000MS Memory Limit:

亦凉/ 2022年06月16日 14:53/ 0 赞/ 177 阅读

相关【费马小定理降幂+矩阵快速幂+快速幂】M斐波那契数列 HDU - 4549

Think: 1知识点：费马小定理降幂+矩阵快速幂+快速幂（１）：费马小定理降幂：定理：若gcd(A, M) == 1，则A^x = A^(x%Eular(M)

桃扇骨/ 2022年06月07日 11:26/ 0 赞/ 168 阅读

相关欧拉定理费马小定理

欧拉定理： > 若gcd(a,m)=1 g c d ( a , m ) = 1 ，则aφ(m)≡1(modm) a φ ( m ) ≡ 1 ( mod m ) 。其中

本是古典何须时尚/ 2022年06月02日 10:44/ 0 赞/ 195 阅读

相关 Applese 涂颜色（组合数学 + 快速幂 + 费马小定理 + 大数运算）

链接：[https://ac.nowcoder.com/acm/contest/330/E][https_ac.nowcoder.com_acm_contest_330_E]

客官°小女子只卖身不卖艺/ 2022年04月23日 08:30/ 0 赞/ 183 阅读

相关费马小定理测素数

素性测试（Miller-Rabin测试）首先，一个叫费马的人提出：如果一个数p是质数，且gcd(a,p)==1。那么(a^p)%p==a，这就是费马小定理。然后我们反向利

拼搏现实的明天。/ 2022年03月20日 06:16/ 1 赞/ 281 阅读

相关 HDU - 4704 - Sum 【费马小定理 + 快速幂】题解

目录 1.题目 2.代码 1.题目 ![在这里插入图片描述][watermark_type_ZmFuZ3po

川长思鸟来/ 2021年07月24日 20:25/ 0 赞/ 341 阅读