fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. const int mod = (int)13;
  6.  
  7.  
  8. ll mod_pow(ll x, ll n, ll mod){
  9. 	if(n==0) return 1;
  10. 	ll rtn = mod_pow(x * x % mod, n / 2, mod);
  11. 	if(n & 1) rtn = rtn * x % mod;
  12. 	return rtn;
  13. }
  14.  
  15. ll divmod(ll x, ll y, ll mod){ return ( x * mod_pow(y, mod-2, mod)) % mod; }
  16.  
  17. //ブルートフォース
  18. ll bf2(int p, int q, int r, int n){
  19. 	ll a = p;
  20. 	for(int i=1;i<=n;i++){
  21. 	 a = (q*a+r)%mod;
  22. 	}
  23. 	return a%mod;
  24. }
  25. //数列の差分が等比数列なので、等比数列の和から第n項を求める
  26. ll cl(int p, int q, int r, ll n){
  27. 	p%=mod;q%=mod;r%=mod;
  28. 	//if(n==0) return p%mod;
  29.  
  30. 	if(q%mod==1) return (r*n + p)%mod;
  31. 	ll a = (p * q + r - p + mod);
  32. 	ll sm =  a*( mod_pow(q, n, mod) -1 + mod ) ;
  33. 	sm = divmod(sm, q-1 , mod) + mod ;
  34. 	return ( sm + p +mod)%mod;
  35. }
  36. //周期を求めて、剰余で解答(これがbestだった)
  37. ll clz(int p, int q, int r, ll n){
  38. 	if(n==0) return p%mod;
  39. 	int a=p, num=0;
  40. 	vector<int> lp;
  41. 	for(num=0; ; num++){
  42. 		a = (a*q + r)%mod;
  43. 		if(any_of(lp.begin(),lp.end(),[a](int x){return x==a;})) break;
  44. 		lp.push_back(a);
  45. 	}
  46. 	return lp[(n-1)%num];
  47. }
  48.  
  49.  
  50. int main(){
  51.  
  52. 	int p,q,r; ll n;
  53. 	while(cin >>p >>q >>r >>n){
  54. 		printf("%2d %2d %2d %lld ==> %lld\n", p, q,r,n,cl(p,q,r,n));
  55. 	}
  56. 	int wct=0;
  57. 	mt19937 mrt(114568);
  58. 	//周期と等比数列でランダムチェック 100万
  59. 	for(int i=0; i<1000000; i++){
  60. 		p=mrt()%99;q=mrt()%99;r=mrt()%99;n=mrt()%999999999;
  61. 		ll z=cl(p,q,r,n), zz=clz(p,q,r,n);
  62. 		if(z!=zz){
  63. 			wct++;
  64. 			printf("%2d %2d %2d %lld ==> %lld  %lld\n",  p, q,r,n,z,zz);
  65. 		}
  66. 	}	
  67.  
  68. }
  69. /*
  70. 1 2 0 8
  71. 1 0 99 0
  72. 1 2 3 2
  73. 1 3 5 10000000000
  74. 66 23 45 23456
  75.  
  76. */
  77.  
  78.  
Success #stdin #stdout 0.75s 15240KB
comments (?)
stdin
copy 
1 2 0 8
1 0 99 0
1 2 3 2
1 3 5 10000000000
66  23 45 23456
stdout
copy 
 1  2  0 8 ==> 9
 1  0 99 0 ==> 1
 1  2  3 2 ==> 0
 1  3  5 10000000000 ==> 8
66 23 45 23456 ==> 10
https://ideone.com/Y4N5oM
お題スレ Part13 632
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!