Project Euler problem 48 处理乘法取模爆long long的方法

呵呵  这题的猥琐之处在于你用快速幂中间过程都有可能爆了long long 

不过我有处理爆long long 的方法

乘的时候用二分的方法去搞就没问题了。详见代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <cmath>
#include <vector>
#define eps 1e-6
#define INF 1000000007
#define PI acos(-1.0)
using namespace std;
long long mod = 10000000000LL;
long long multi(long long a, long long b, long long c)
{long long ret = 0;while(b){if(b & 1){ret += a;if(ret >= c)ret -= c;}a += a;if(a >= c) a -= c;b >>= 1;}return ret;
}
long long fastmod(long long a, long long b, long long c)//a^b mod c
{long long ret = 1;a %= c;for (; b; b >>= 1, a = multi(a, a, c))if (b & 1)ret = multi(ret, a, c);return ret;
}int main()
{long long sum = 0;for(int i = 1; i <= 1000; i++)sum = (sum + fastmod(i, i, mod)) % mod;cout << sum << endl;return 0;
}