hdu 4704 Sum（费马小定理）

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

数论，费马小定理 a^(p-1) % p == 1，长见识了

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef __int64 ll;
const int MAXN = 100005;
char s[MAXN];
const ll mod = 1000000007;
ll n;
ll power(ll x, ll t)
{ll res = 1; ll tp = x;while (t){if (t & 1) res = res*tp%mod;tp = tp*tp%mod;t >>= 1;}return res;
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);
#endifwhile (scanf("%s", s) != EOF){n = 0;int k = strlen(s);for (int i = 0; i < k; ++i){n = (n*10 + s[i] - '0')%(mod-1);}n = (n-1+mod-1)%(mod-1);printf("%I64d\n", power(2, n));} return 0;
}

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

---