fork download
copy 
  1. /*
  2. プログラミングのお題スレ Part13
  3. https://m...content-available-to-author-only...h.net/test/read.cgi/tech/1549160513/
  4.  
  5. 632デフォルトの名無しさん2019/03/12(火) 19:26:28.38ID:mUEXbKn8
  6. お題 
  7. 数列a[i]を考える。 
  8. a[0] = p 
  9. a[i+1] = q * a[i] + r 
  10.  
  11. [入力] 
  12. p q r n 
  13. (p,q,r,nは整数) 
  14. (0≦p,q,r≦99) 
  15. (0≦n≦10^10) 
  16.  
  17. [出力] 
  18. a[n] mod 13 を求めよ 
  19.  
  20. 1 2 0 8 
  21. => 9 (2^8 mod 13) 
  22.  
  23. 1 0 99 0 
  24. => 1 
  25.  
  26. 1 2 3 2 
  27. => 0 (a[0]=1, a[1]=2*1+3=5, a[2]=2*5+3=13) 
  28.  
  29. 1 3 5 10000000000 
  30. => ?
  31. */
  32.  
  33. #include <stdio.h>
  34. #include <stdlib.h>
  35. #define DEFAULT_MOD_NUM 13 //デフォルトの剰余、13以外では動作未確認
  36.  
  37. int main(int argc, char *argv[]){
  38.   int p;
  39.   int q;
  40.   int r;
  41.   int n;
  42.   scanf("%d",&p);
  43.   scanf("%d",&q);
  44.   scanf("%d",&r);
  45.   scanf("%d",&n);
  46.  
  47.   int a[(DEFAULT_MOD_NUM - 1) * 2]; //数列の範囲, MOD-1の周期になるっぽい, 周期数を調べるため2倍の長さを取得
  48.   int length = (DEFAULT_MOD_NUM - 1) * 2; //配列の長さ
  49.   int period; //周期
  50.  
  51.   int flag; //フラグ用
  52.   int ci;   //カウンタ
  53.   int cj;   //カウンタ
  54.  
  55.   //データ入力値の確認
  56.   flag = 0;
  57.   if( !(p >= 0) ){
  58.     puts("pの値が不正です。0≦ pを満たす必要があります");
  59.     flag = 1;
  60.   }
  61.   if( !(r <= 99) ){
  62.     puts("rの値が不正です。r≦ 99を満たす必要があります。");
  63.     flag = 1;
  64.   }
  65.   if( !(0 <= n && n <= 10000000000) ){
  66.     puts("nの値が不正です。0≦ n≦ 10^10を満たす必要があります。");
  67.     flag = 1;
  68.   }
  69.   if(flag == 1){
  70.     exit(1);  
  71.   }
  72.  
  73.   //数列を計算
  74.   a[0] = p;
  75.   for(ci = 1; ci < length; ci++){
  76.     a[ci] = (q * a[ci - 1] + r) % DEFAULT_MOD_NUM;
  77.   }
  78.  
  79.   //数列の周期を調べる
  80.   for(ci = 0; ci < DEFAULT_MOD_NUM - 1; ci++){
  81.     flag = 1;
  82.     for(cj = 0; cj < length; cj++){
  83.       if(a[cj] != a[cj % (ci + 1)]){
  84. 	flag = 0;
  85. 	break;
  86.       }
  87.     }
  88.  
  89.     if(flag == 1){
  90.       period = ci + 1;
  91.       break;
  92.     }
  93.  
  94.     //一応DEFAULT_MOD_NUM-1以上の周期は無いはずだが、発生した場合、終了する。
  95.     if(ci > DEFAULT_MOD_NUM){
  96.       printf("ci = %d\n",ci);
  97.       puts("周期がDEFAULT_MOD_NUM-1を超えました。終了します。");
  98.       exit(1);
  99.     }
  100.   }
  101.  
  102.   //数列の「nの周期数による剰余」番目の項が答え。
  103.   printf("=> %d\n", a[(n % period)]);
  104.  
  105.   return 0;
  106. }
  107.  
Success #stdin #stdout 0s 9424KB
comments (?)
stdin
copy 
1
3
5
1000000000
stdout
copy 
=> 8
https://ideone.com/m3vejt
language:
C (gcc 8.3)
created:
5 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!