数论 --- 费马小定理 + 快速幂 HDU 4704 Sum
Sum
Problem's Link: http://acm.hdu.edu.cn/showproblem.php?pid=4704
Mean:
给定一个大整数N，求1到N中每个数的因式分解个数的总和。
analyse:
N可达10^100000，只能用数学方法来做。
首先想到的是找规律。通过枚举小数据来找规律，发现其实answer=pow(2,n-1);
分析到这问题就简单了。由于n非常大,所以这里要用到费马小定理:a^n ≡ a^(n%(m-1)) * a^(m-1)≡ a^(n%(m-1)) (mod m) 来优化一下，不然直接用快速幂会爆。
Time complexity: O(n)
Source code:
/* * this code is made by crazyacking * Verdict: Accepted * Submission Date: 2015-05-22-21.21 * Time: 0MS * Memory: 137KB */ #include <queue> #include <cstdio> #include <set> #include <string> #include <stack> #include <cmath> #include <climits> #include <map> #include <cstdlib> #include <iostream> #include <vector> #include <algorithm> #include <cstring> #define LL long long #define ULL unsigned long long using namespace std; const int mod=1e9+7; const int MAXN=100010; char s[MAXN]; long long quickPower(long long a,long long b,long long m) { long long ans=1; while(b) { if(b&1) ans=(ans*a)%m,b--; b/=2,a=a*a%m; } return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); while(~scanf("%s",s)) { ULL n=0; for(int i=0;s[i];++i) n=(n*10+s[i]-'0')%(mod-1); printf("%d\n",(int)quickPower(2,((n-1)%(mod-1))%mod,mod)); } return 0; } /* */