結果

問題 No.251 大きな桁の復習問題(1)
ユーザー asugen0402
提出日時 2019-06-10 14:05:48
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 5 ms / 5,000 ms
コード長 5,393 bytes
コンパイル時間 318 ms
コンパイル使用メモリ 33,280 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-06 00:37:21
合計ジャッジ時間 1,173 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
// 内部定数
#define D_MOD           129402307                               // 除数
#define D_CHAR_MAX      100005                                  // 最大文字数
#define D_VAL_UNIT      1000000000                              // 値 - 単位
#define D_VAL_CNT       20000                                   // 値 - 数
// 内部構造体 - 値情報
typedef struct Val {
    long long ml1Val[D_VAL_CNT];                                // 値 [0]:最小桁 [0>]:上位桁
    int miVCnt;                                                 // 値数
    int miSign;                                                 // 符号 1 or -1
} Val;
// 内部変数
static FILE *szpFpI;                                            // 入力
static char sc1N[D_CHAR_MAX], sc1M[D_CHAR_MAX];                 // N, M
// 内部変数 - テスト用
#ifdef D_TEST
    static int siRes;
    static FILE *szpFpA;
    static int siTNo;
#endif
// 出力
int
fOut(
    char *pcpLine               // <I> １行
)
{
    char lc1Buf[1024];
#ifdef D_TEST
    fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
    if (strcmp(lc1Buf, pcpLine)) {
        siRes = -1;
    }
#else
    printf("%s", pcpLine);
#endif
    return 0;
}
// 値 - 調整
int
fValAdjK(
    Val *pzpVal                 // <I> 値
)
{
    // 値数
    if (pzpVal->ml1Val[pzpVal->miVCnt] != 0) {
        pzpVal->miVCnt++;
    }
    if (pzpVal->ml1Val[pzpVal->miVCnt - 1] == 0) {
        pzpVal->miVCnt--;
    }
    // 符号
    if (pzpVal->ml1Val[pzpVal->miVCnt - 1] > 0) {
        pzpVal->miSign = 1;
    }
    else if (pzpVal->ml1Val[pzpVal->miVCnt - 1] < 0) {
        pzpVal->miSign = -1;
    }
    else {
        pzpVal->miSign = 0;
    }
    return 0;
}
int
fValAdj(
    Val *pzpVal                 // <I> 値
)
{
    int i;
    // 単位
    for (i = 0; i < pzpVal->miVCnt; i++) {
        pzpVal->ml1Val[i + 1] += pzpVal->ml1Val[i] / D_VAL_UNIT;
        pzpVal->ml1Val[i] %= D_VAL_UNIT;
        fValAdjK(pzpVal);
    }
    // 符号統一
    for (i = pzpVal->miVCnt - 2; i >= 0; i--) {
        int liSign;
        if (pzpVal->ml1Val[i] > 0) {
            liSign = 1;
        }
        else if (pzpVal->ml1Val[i] > 0) {
            liSign = -1;
        }
        else {
            continue;
        }
        if (liSign == pzpVal->miSign) {
            continue;
        }
        pzpVal->ml1Val[i] += D_VAL_UNIT * pzpVal->miSign;
        pzpVal->ml1Val[i + 1] -= pzpVal->miSign;
        fValAdjK(pzpVal);
    }
    return 0;
}
// 値 - 作成
int
fValMakeS(
    char *pcpVal                // <I> 値の文字列
    , Val *pzpVal               // <I> 作成値
)
{
    char lc1Buf[1024];
    // 初期化
    memset(pzpVal, 0, sizeof(Val));
    // 取得文字数
    int liCCnt = 0;
    int liVal = D_VAL_UNIT;
    while (liVal >= 10) {
        liVal /= 10;
        liCCnt++;
    }
    // 文字列開始位置・符号
    int liSNo, liSign;
    if (pcpVal[0] == '-') {
        liSNo = 1;
        liSign = -1;
    }
    else {
        liSNo = 0;
        liSign = 1;
    }
    // 文字列終了位置
    int liENo = -1;
    for (liENo = liSNo; ; liENo++) {
        if (pcpVal[liENo] < '0' || '9' < pcpVal[liENo]) {
            liENo--;
            break;
        }
    }
    // 値 - 取得
    while (liENo >= liSNo) {
        int liNo = liENo - liCCnt + 1;
        if (liNo < liSNo) {
            liCCnt += liNo - liSNo;
            liNo = liSNo;
        }
        liENo -= liCCnt;
        memcpy(lc1Buf, &pcpVal[liNo], liCCnt);
        lc1Buf[liCCnt] = '\0';
        sscanf(lc1Buf, "%lld", &pzpVal->ml1Val[pzpVal->miVCnt]);
        pzpVal->ml1Val[pzpVal->miVCnt] *= liSign;
        pzpVal->miVCnt++;
    }
    // 値 - 調整
    fValAdj(pzpVal);
    return 0;
}
// 値 - 剰余
long long
fValMod(
    Val *pzpVal                 // <I> 値
    , long long plMod           // <I> 剰余値
)
{
    int i;
    long long llVal = 0;
    for (i = pzpVal->miVCnt - 1; i >= 0; i--) {
        llVal *= D_VAL_UNIT;
        llVal += pzpVal->ml1Val[i];
        llVal %= plMod;
    }
    return llVal;
}
// べき乗 - 取得
int
fGetModPower(
    int piBase                  // <I> 基数
    , int piIdx                 // <I> 指数
)
{
    // 平方リスト - 作成
    int li1Val[100];
    li1Val[0] = piBase;
    int liCnt = 1;
    int liIdx = 1;
    while (piIdx > liIdx) {
        li1Val[liCnt] = (int)((long long)li1Val[liCnt - 1] * (long long)li1Val[liCnt - 1] % (long long)D_MOD);
        liCnt++;
        liIdx += liIdx;
    }
    // べき乗 - 取得
    int liVal = 1;
    while (piIdx > 0) {
        if (piIdx >= liIdx) {
            piIdx -= liIdx;
            liVal = (int)((long long)liVal * (long long)li1Val[liCnt - 1] % (long long)D_MOD);
        }
        liCnt--;
        liIdx /= 2;
    }
    return liVal;
}
// 実行メイン
int
fMain(
)
{
    Val lzVal;
    // N - 取得
    fgets(sc1N, sizeof(sc1N), szpFpI);
    if (sc1N[0] == '0') {
        return 0;
    }
    fValMakeS(sc1N, &lzVal);
    int liN = (int)fValMod(&lzVal, D_MOD);
    // M - 取得
    fgets(sc1M, sizeof(sc1M), szpFpI);
    if (sc1M[0] == '0') {
        return 1;
    }
    fValMakeS(sc1M, &lzVal);
    int liM = (int)fValMod(&lzVal, D_MOD - 1);
    if (liM == 0) {
        if (liN == 0) {
            return 0;
        }
        else {
            return 1;
        }
    }
    // NのM乗
    return fGetModPower(liN, liM);
}
// １回実行
int
fOne(
)
{
    int liRet;
    char lc1Buf[1024];
    // 入力 - セット
#ifdef D_TEST
    sprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);
    szpFpI = fopen(lc1Buf, "r");
    sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);
    szpFpA = fopen(lc1Buf, "r");
    siRes = 0;
#else
    szpFpI = stdin;
#endif
    // 実行メイン
    liRet = fMain();
    // 出力
    sprintf(lc1Buf, "%d\n", liRet);
    fOut(lc1Buf);
    // 残データ有無
#ifdef D_TEST
    lc1Buf[0] = '\0';
    fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
    if (strcmp(lc1Buf, "")) {
        siRes = -1;
    }
#endif
    // テストファイルクローズ
#ifdef D_TEST
    fclose(szpFpI);
    fclose(szpFpA);
#endif
    // テスト結果
#ifdef D_TEST
    if (siRes == 0) {
        printf("OK %d\n", siTNo);
    }
    else {
        printf("NG %d\n", siTNo);
    }
#endif
    return 0;
}
// プログラム開始
int
main()
{
#ifdef D_TEST
    int i;
    for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
        siTNo = i;
        fOne();
    }
#else
    fOne();
#endif
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0