結果

問題 No.28 末尾最適化
ユーザー mudbdbmudbdb
提出日時 2015-07-21 22:12:44
言語 C90
(gcc 11.4.0)
結果
AC  
実行時間 628 ms / 5,000 ms
コード長 3,616 bytes
コンパイル時間 513 ms
コンパイル使用メモリ 25,088 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-08 11:38:26
合計ジャッジ時間 1,284 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 0 ms
6,816 KB
testcase_01 AC 628 ms
6,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:118:3: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  118 |   scanf("%d", &Q);
      |   ^~~~~~~~~~~~~~~
main.c:125:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  125 |     scanf("%d", &(seed[i]));
      |     ^~~~~~~~~~~~~~~~~~~~~~~
main.c:126:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  126 |     scanf("%d", &(N[i]));
      |     ^~~~~~~~~~~~~~~~~~~~
main.c:127:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  127 |     scanf("%d", &(K[i]));
      |     ^~~~~~~~~~~~~~~~~~~~
main.c:128:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  128 |     scanf("%d", &(B[i]));
      |     ^~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
int *Order = 0;
int Order_n = 0;
int cmp(const void* a, const void* b)
{
  int rc;
  int i;
  for (i=0; i<Order_n; i++) {
    rc = ((int*)a)[Order[i]] - ((int*)b)[Order[i]];
    if (rc != 0) {
      break;
    }
  }
  return rc;
}
void factor(int N, int* pr, int *pow, int *nu)
{
  (*nu) = 0;
  int pw;
  for (pw=0; N%2==0; pw++) {
    N/=2;
  }
  if (pw != 0) {
    pr[*nu] = 2;
    pow[*nu] = pw;
    (*nu)++;
  }
  int i;
  for (i=3; i*i<=N; i+=2) {
    for (pw=0; N%i==0; pw++) {
      N/=i;
    }
    if (pw != 0) {
      pr[*nu] = i;
      pow[*nu] = pw;
      (*nu)++;
    }
  }
  if (N != 1) {
    pr[*nu] = N;
    pow[*nu] = 1;
    (*nu)++;
  }
  return;
}
void genX(int seed, int N, int *X)
{
  //100000009 = 149 * 671141;
  int mod = 100000009;
  long long int Y, Z;
  int i;
  X[0] = seed;
  for (i=1; i<=N; i++) {
    Y = X[i-1];
    Y = Y*Y;
    Z = X[i-1];
    Z = Z*12345;
    Y += Z;
    Y %= mod;
    X[i] = 1 + Y;
  }
  return;
}
int **P;
int P_i;
int *A;
void perm(int depth, int no, int N)
{
  int i;
  int j;
  if (depth < N) {
    A[depth] = no;
    int i;
    for (i=0; i<N; i++) {
      for (j=0; j<=depth; j++) {
        if (i == A[j]) {
          goto SKIP;
        }
      }
      perm(depth+1, i, N);
      SKIP:
      ;
    }
    if (depth == N-1) {
      for (i=0; i<N; i++) {
        P[P_i][i] = A[i];
      }
      P_i++;
    }
  }
  return;
}
int **genP(int N)
{
  int NN = 1;
  int i;
  int j;
  for (i=1; i<=N; i++) NN*=i;
  P = (int**)malloc(sizeof(int*)*NN);
  P[0] = (int*)malloc(sizeof(int)*NN*N);
  for (i=1; i<NN; i++) P[i] = &(P[i-1][N]);
  A = (int*)malloc(sizeof(int)*N);
  P_i = 0;
  for (i=0; i<N; i++) {
    perm(0, i, N);
  }
  free(A); A=0;
  return P;
}
int main()
{
  int Q;
  int *seed;
  int *N;
  int *K;
  int *B;
  scanf("%d", &Q);
  seed = (int*)malloc(sizeof(int)*Q);
  N = (int*)malloc(sizeof(int)*Q);
  K = (int*)malloc(sizeof(int)*Q);
  B = (int*)malloc(sizeof(int)*Q);
  int i;
  for (i=0; i<Q; i++) {
    scanf("%d", &(seed[i]));
    scanf("%d", &(N[i]));
    scanf("%d", &(K[i]));
    scanf("%d", &(B[i]));
  }

  int maxN = 0;
  for (i=0; i<Q; i++) if (maxN < N[i]) maxN = N[i];
  int *X = (int*)malloc(sizeof(int)*(maxN+1));

  int maxB = 0;
  for (i=0; i<Q; i++) if (maxB < B[i]) maxB = B[i];
  int pr_n;
  for (i=1,pr_n=0; i<maxB; i*=2,pr_n++) ;
  pr_n++;
  int *pr = (int*)malloc(sizeof(int)*pr_n);
  int *pow = (int*)malloc(sizeof(int)*pr_n);
  Order = (int*)malloc(sizeof(int)*pr_n);
  int **Xpow = (int**)malloc(sizeof(int*)*(maxN+1));
  Xpow[0] = (int*)malloc(sizeof(int)*(maxN+1)*pr_n);
  int ***P = (int***)malloc(sizeof(int**)*pr_n);
  for (i=0; i<pr_n; i++) P[i] = 0;
  pr_n = 0;

  int total;
  int ans;
  int j;
  int k;
  int l;
  int P_n;
  for (i=0; i<Q; i++) {
    factor(B[i], pr, pow, &pr_n);
    genX(seed[i], N[i], X);
    for (j=1; j<=N[i]; j++) Xpow[j] = &(Xpow[j-1][pr_n]);
    for (j=0; j<=N[i]; j++) {
      for (k=0; k<pr_n; k++) {
        for (Xpow[j][k] = 0; X[j]%pr[k]==0; Xpow[j][k]++) {
          X[j]/=pr[k];
        }
      }
    }

    if (P[pr_n-1] == 0) {
      P[pr_n-1] = genP(pr_n);
    }
    ans = ~(1 << 31);
    Order_n = pr_n;
    P_n = 1;
    for (l=1; l<=pr_n; l++) P_n*=l;
    for (l=0; l<P_n; l++) {
      for (k=0; k<pr_n; k++) {
        Order[k] = P[pr_n-1][l][k];
      }
      qsort(Xpow[0], N[i]+1, sizeof(int)*pr_n, cmp);
      for (k=0; k<pr_n; k++) {
        total = 0;
        for (j=0; j<K[i]; j++) {
          total += Xpow[j][k];
        }
        if (total/pow[k] < ans) ans = total/pow[k];
      }
    }

    printf("%d\n", ans);
  }
  return 0;
}
0