fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. long long D = 1000000;
  5.  
  6. /*
  7.     Return a^n (mod p)
  8. */
  9. long long PowMod(long long a, long long n, long long p) {
  10. 	if (n == 0) return 1;
  11. 	if (n % 2 == 0) return PowMod(a * a % p, n / 2, p);
  12. 	return a * PowMod(a, n - 1, p) % p;
  13. }
  14.  
  15. /*
  16.     一次合同式 a*x=b (mod n: 正整数) の解を x=r (mod m) の形で求める.
  17.     解が存在すれば true, しなければ false を返す.
  18.     参考: http://h...content-available-to-author-only...y.com/docs/algo/c/congruence.html
  19. */
  20. bool LinearCongruence(long long a, long long b, long long n, long long &m, long long &r)
  21. {
  22. 	long long x = a, y = n, z = b, w = 0, s, tmp;
  23. 	while ((s = x % y) != 0) {
  24. 		r = x / y;
  25. 		x = y;
  26. 		y = s;
  27. 		tmp = w;
  28. 		w = z - r * w;
  29. 		z = tmp;
  30. 	}
  31. 	if (b % y != 0) return false;
  32. 	r = (w / y) % (n / y);
  33. 	if (r < 0) r += n / y;
  34. 	m = n / y;
  35. 	return true;
  36. }
  37.  
  38. long long Solve(long long n) {
  39.     long long s = (2 * (PowMod(16, n, D) - 1)) % D;
  40.     long long m, r;
  41.     LinearCongruence(3, s, D, m, r);
  42.     return r;
  43. }
  44.  
  45. int main(int argc, char *argv[])
  46. {
  47.     cout.precision(16);
  48.     long long n = 4;
  49.     cin >> n;
  50.  
  51.     cout << Solve(n) << endl;
  52. }
Success #stdin #stdout 0s 3420KB
comments (?)
stdin
copy 
10000000000
stdout
copy 
406250
https://ideone.com/vXZNDs
「エース・ナンバー」問題 解法２
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!