（扩展）欧拉定理例题汇总

发表于 更新于 分类于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

hdu 4704 Sum

Problem Description

For gievn N,let S(k) be the number of $ (x_1, x_2, \cdots ,x_k) $ which:
$ x_1, x_2, \cdots ,x_k \in \mathbb{Z}^+$
$ x_1 + x_2 + \cdots + x_k = N $
Find $ (S(1)+S(2)+\cdots+S(N)) \;mod\;(10^9+7)$.

Input

The first line contains an integer N. $(1\leq N\leq 10^{100000}) $

Output

An integer denotes the values.

Sample Input

1
2

Sample Output

1
2

Hint

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

思路：

$S(i)$ 表示将N划分为i个数的方案数，举个栗子：
当N=4时，S(1)=4,1种方案；S(2)=1+3=3+1,2种方案；
S(3)=1+1+2=1+2+1=2+1+1,3种方案；
S(4)=1+1+1+1,1种方案,一共7种方案。
那么原问题就转化成小球隔板问题：将N个1排成一行，有N-1个空，每个空可以选择插入或者不插入一块隔板，则一共有 $2^{N-1}$ 种方案数。因为指数非常大，且 $\gcd(2,10^9+7)=1$，所以要用扩展欧拉定理来降幂，即 $ 2^{(N-1)\%\varphi(1e9+7)} \;(mod\;1e9+7)$。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1e9+7;
string str; LL n, phi;
LL quick_mod(LL a, LL b) {
    LL res = 1LL;
    while(b) {
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
int main() {
    while(cin >> str) {
        n = 0LL, phi = mod - 1LL;
        for(int i = 0; str[i]; ++i) n = (n * 10LL + (str[i] - '0')) % phi; //φ(p) = p - 1
        cout << quick_mod(2LL, n - 1LL) << endl; // 2^(n - 1) % p
    }
    return 0;
}
0%