Submission #4050485


Source Code Expand

#pragma optimization_level 3
#include <iostream>
#include <algorithm>
using namespace std;


using QWORD = unsigned long long;
using SQWORD = long long;
using DWORD = unsigned int;
using SDWORD = int;
using WORD = unsigned short;
using SWORD = short;
using BYTE = unsigned char;
using SBYTE = char;
using DOUBLE = double;
using FLOAT = float;

#define MIN_SDWORD (-2147483648)
#define MAX_SDWORD (2147483647)
#define MIN_SBYTE (-128)
#define MAX_SBYTE (127)

#define MIN_SQWORD (0x8000000000000000)
#define MAX_SQWORD (0xFFFFFFFFFFFFFFFF)

#define MAX_QWORD  (0xFFFFFFFFFFFFFFFF)
#define MAX_DWORD  (0xFFFFFFFF)
#define MAX_WORD   (0xFFFF)
#define MAX_BYTE   (0xFF)


#define rep(i, n) for (int i=0; i<int(n); i++)
#define all(c) (c).begin(), (c).end()
#define _1 first
#define _2 second
#define pb push_back
 
int X, P, A, B;

#if 0
int modpow(int x, int k) {
  int a = 1;
  while (k) {
    if (k & 1) a = (1LL*a*x) % P;
    x = (1LL*x*x) % P;
    k >>= 1;
  }
  return a;
}
#endif

static DWORD powMod(DWORD x, DWORD k, DWORD m)
{
    DWORD dwRes = 1;
    while (k > 0) {
        if (k & 1) {
            dwRes = ((QWORD)dwRes * (QWORD)x) % (QWORD)m;
            --k;
        } else {
            x = ((QWORD)x * (QWORD)x) % (QWORD)m;
            k >>= 1;
        }   
    }
    return dwRes % m;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> X >> P >> A >> B;
    QWORD s = powMod(X, A, P);
    QWORD m = s;
    for (DWORD dwI = 0; dwI < B-A; dwI++) {
        s = (1LL*s*X) % P;
        m = min(m, s);
        if (m == 1) break;
    }
    printf("%d\n", m);
    return 0;
}

Submission Info

Submission Time
Task D - あまり
User yeye
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1683 Byte
Status AC
Exec Time 2621 ms
Memory 256 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:77:21: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘QWORD {aka long long unsigned int}’ [-Wformat=]
     printf("%d\n", m);
                     ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 4
AC × 23
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All sample_02.txt, sample_03.txt, sample_04.txt, subtask1_00.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 6 ms 256 KB
sample_04.txt AC 1 ms 256 KB
subtask1_00.txt AC 1017 ms 256 KB
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 3 ms 256 KB
subtask1_04.txt AC 72 ms 256 KB
subtask1_05.txt AC 1 ms 256 KB
subtask1_06.txt AC 1 ms 256 KB
subtask1_07.txt AC 1 ms 256 KB
subtask1_08.txt AC 1 ms 256 KB
subtask1_09.txt AC 2 ms 256 KB
subtask1_10.txt AC 1 ms 256 KB
subtask1_11.txt AC 555 ms 256 KB
subtask1_12.txt AC 3 ms 256 KB
subtask1_13.txt AC 1 ms 256 KB
subtask1_14.txt AC 1 ms 256 KB
subtask1_15.txt AC 603 ms 256 KB
subtask1_16.txt AC 1 ms 256 KB
subtask1_17.txt AC 1 ms 256 KB
subtask1_18.txt AC 1 ms 256 KB
subtask1_19.txt AC 2621 ms 256 KB