Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <iostream>
- #include <cmath>
- unsigned long long mulmod(unsigned long long a, unsigned long long b, unsigned long long mdlo) {
- a %= mdlo;
- b %= mdlo;
- if (a <= 0xFFFFFFF && b <= 0xFFFFFFF) {
- return (a * b) % mdlo;
- }
- unsigned int leadingZeros = 0;
- unsigned long long m = mdlo;
- while((m & 0x8000000000000000ULL) == 0) {
- leadingZeros++;
- m <<= 1;
- }
- unsigned long long mask = (1 << leadingZeros) - 1;
- unsigned long long result = 0;
- while(a > 0 && b > 0) {
- result += (b & mask) * a;
- result %= mdlo;
- b >>= leadingZeros;
- a <<= leadingZeros;
- a %= mdlo;
- }
- return result;
- }
- unsigned long long powmod(unsigned long long base, unsigned long long expo, unsigned long long mdlo) {
- unsigned long long result = 1;
- while (expo > 0) {
- if (expo & 1) {
- result = mulmod(result, base, mdlo);
- }
- base = mulmod(base, base, mdlo);
- expo >>= 1;
- }
- return result;
- }
- int main() {
- unsigned int N;
- std::cin >> N;
- const unsigned long long TenDigits = 10000000000ULL;
- unsigned long long sum = 0;
- for(unsigned int i = 1; i <= N; i++) {
- sum += powmod(i, i, TenDigits);
- }
- std::cout << (sum % TenDigits) << std::endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement