fork download
copy 
  1. #include <iostream>
  2. #define MIN(a,b)		((a)<(b)?(a):(b))
  3. using namespace std;
  4. long long D = 1000000;
  5. int c[1000000];
  6.  
  7. long long Solve(long long n) {
  8. 	int a = 1, p = 0, q = 0, r = 0, s = 0;
  9. 	for (int i = 0; i < D; i++) c[i] = -1;
  10. 	for (;; p ++) {
  11. 		if (c[a] != -1) break;
  12. 		c[a] = p;
  13. 		a = (a * 16) % D;
  14. 	}
  15. 	q = c[a];
  16. 	p -= q;
  17. 	s = a;
  18. 	cout << "数列 a(n)=16^n mod 10^6 は, n=" << q << " 以降, 周期 " << p << " で循環する." << endl;
  19. 	cout << "つまり, a(n+" << p << ") = a(n) (ただし, n≧" << q << ")." << endl;
  20. 	for (int i = 0; i < p; i++) {
  21. 		r = (r + a) % D;
  22. 		a = (a * 16) % D;
  23. 	}
  24. 	cout << "a(" << q << ") から a(" << q << "+" << p << ") までの和 mod 10^6 は " << r << endl;
  25. 	long long answer = 0;
  26. 	for (int i = 0, a = 1; i < MIN(n,q); i++) {
  27. 		answer = (answer + a) % D;
  28. 		a = (a * 16) % D;
  29. 	}
  30. 	answer += ((n - q) / p) * r;
  31. 	for (int i = 0; i < (n - q) % p; i++) {
  32. 		answer = (answer + s) % D;
  33. 		s = (s * 16) % D;
  34. 	}
  35. 	return (answer * 10) % D;
  36. }
  37.  
  38. int main(int argc, char *argv[])
  39. {
  40.     cout.precision(16);
  41.     long long n;
  42.     cin >> n;
  43.  
  44.     cout << Solve(n) << endl;
  45. }
  46.  
Success #stdin #stdout 0s 7324KB
comments (?)
stdin
copy 
10000000000
stdout
copy 
数列 a(n)=16^n mod 10^6 は, n=2 以降, 周期 3125 で循環する.
つまり, a(n+3125) = a(n) (ただし, n≧2).
a(2) から a(2+3125) までの和 mod 10^6 は 800000
406250
https://ideone.com/EuTVoR
「エース・ナンバー」問題 解法１
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!