上完厕所后, 蒜头君的手机欠费了, 于是他来到了中国移动营业厅. 正当他准备交钱时, 突然发现钱包不见了.
"奇怪, 今天出门时明明带了钱包." 蒜头君自言自语道.
"别着急, 今天推出了一个新活动. 只要计算出这道题的答案, 就送 999999 元话费" 工作人员指着一块公告牌耐心地说.
只见公告牌上写着, 计算 1^{2019}+2^{2019}+3^{2019}+\ldots+n^{2019}12019+22019+32019+...+n2019 对 1008610086 取模的结果, 其中 n=10^{12}n=1012.
请你帮助蒜头君计算答案.
题解:
因为 n^2019 = (n%10086)^2019, 所以每 10086 个数的 2019 次方的和都是相等的
即 ans = 1^2019+2^2019+...+10086^2019 = 10087^2019+10088^2019+...+2*10086^2019
因此 10^12 中有 n^12/10086 个完整周期, 这些完整周期的和是单个周期和 ans 乘以周期数
最后再加上不足一个周期的其他数的和就是答案
- #include <map>
- #include <set>
- #include <stack>
- #include <cmath>
- #include <queue>
- #include <cstdio>
- #include <vector>
- #include <string>
- #include <bitset>
- #include <cstring>
- #include <iomanip>
- #include <iostream>
- #include <algorithm>
- #define ls (r<<1)
- #define rs (r<<1|1)
- #define debug(a) cout << #a << " " << a << endl
- using namespace std;
- typedef long long ll;
- const ll maxn = 1e6+10;
- const ll mod = 10086;
- const double pi = acos(-1.0);
- const double eps = 1e-8;
- ll qow( ll a, ll b ) {
- ll ans = 1;
- while( b ) {
- if( b&1 ) {
- ans = ans*a%mod;
- }
- a = a*a%mod;
- b /= 2;
- }
- return ans;
- }
- int main() {
- ll ans = 0, t = 1e12;
- for( ll i = 1; i <= mod; i ++ ) {
- ans = (ans+qow(i%mod,2019))%mod;
- }
- ans = ans*(t/mod)%mod;
- t = t%mod;
- for( ll i = 1; i <= t; i ++ ) {
- ans = (ans+qow(i%mod,2019))%mod;
- }
- cout << ans << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2990931.html