HDU - 4704 Sum （费马小定理 + 快速幂）

本文主要是介绍HDU - 4704 Sum （费马小定理 + 快速幂），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

    
2 

    
2 

Hint

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

题意：求1-n中，组成n的不同种数

思路：首先我们要先推出这个公式：2^(n-1)是结果，结果的推论是：我们想象n个1排一排，  那么我们能用隔板法得到的结果是C(n-1, 0), C(n-1, 1) ..... 所以结果就是2^(n-1)了

但是n那么大，显然不是我们能处理来的，所以这里用到了

费马小定理：：假如a是一个整数，p是一个质数，如果a不是p的倍数，这个定理也可以写成

所以我们将n拆成多个 a*(p-1) + k 的话，那么2^n = 2^[a*(p-1) + k ] % M = 2^k % M,然后就是再减一处理的快速幂取模了

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;
const ll M = 1e9+7;char str[1000010];ll cal(ll m) {int len = strlen(str);ll ans = 0;for (int i = 0; i < len; i++) ans = (ans * 10 + str[i] - '0') % m;return ans;
}ll pow_mod(ll a, ll b) {ll ans = 1;while (b) {if (b & 1)ans = ans * a % M;a = a * a % M;b >>= 1;}return ans;
}int main() {while (scanf("%s", str) != EOF) {ll k = cal(M-1);cout << pow_mod(2, k-1) << endl;}return 0;
}

这篇关于HDU - 4704 Sum （费马小定理 + 快速幂）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！