Submission #4050588
Source Code Expand
#pragma GCC optimize ("O3") #include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <queue> #include <algorithm> #include <map> 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 ArrayLength(a) (sizeof(a) / sizeof(a[0])) static inline QWORD MAX(QWORD a, QWORD b) { return a > b ? a : b; } static inline DWORD MAX(DWORD a, DWORD b) { return a > b ? a : b; } static inline SDWORD MAX(SDWORD a, SDWORD b) { return a > b ? a : b; } static inline QWORD MIN(QWORD a, QWORD b) { return a < b ? a : b; } static inline DWORD MIN(DWORD a, DWORD b) { return a < b ? a : b; } static inline SDWORD MIN(SDWORD a, SDWORD b) { return a < b ? a : b; } #define BYTE_BITS (8) #define WORD_BITS (16) #define DWORD_BITS (32) #define QWORD_BITS (64) using M_BOOL = bool; #define M_TRUE (true) #define M_FALSE (false) #define DIVISOR (1000000007) #define MAX_FACTORY (60) static DWORD adwFactoryNum[MAX_FACTORY]; static DWORD adwFactoryCumMul[MAX_FACTORY]; static DWORD s_dwFactoryNum = 0; static inline void inputString(char *pcStr) { char *pcCur = pcStr; for (;;) { char c = getchar(); if (('\n' == c) || (EOF == c)) { break; } *pcCur = c; pcCur++; } *pcCur = '\0'; } static inline SDWORD inputSDWORD(void) { SDWORD lNumber = 0; SDWORD lMultiplier = 1; M_BOOL bRead = M_FALSE; for (;;) { char c = getchar(); if (!bRead) { if ('-' == c) { lMultiplier = -1; } } if (('0' <= c) && (c <= '9')) { lNumber *= 10; lNumber += (c - '0'); bRead = M_TRUE; } else { if (bRead) { return lNumber * lMultiplier; } } } } static inline DOUBLE inputFP(void) { DOUBLE dInt = 0.0; DOUBLE dFrac = 0.0; DOUBLE dMultiplier = 1.0; DWORD dwFpCnt = 0; DOUBLE *pdCur = &dInt; M_BOOL bRead = M_FALSE; for (;;) { char c = getchar(); if (!bRead) { if ('-' == c) { dMultiplier = -1; } } if ('.' == c) { pdCur = &dFrac; } else if (('0' <= c) && (c <= '9')) { (*pdCur) *= 10; (*pdCur) += (DOUBLE)(c - '0'); bRead = M_TRUE; if (pdCur == &dFrac) { dwFpCnt++; } } else { if (bRead) { return dMultiplier * (dInt + dFrac / (pow((DOUBLE)10.0 , (DOUBLE)dwFpCnt))); } } } } int X, P, A, B; 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; } int main(void) { X = inputSDWORD(); P = inputSDWORD(); A = inputSDWORD(); B = inputSDWORD(); QWORD qwMod = powMod(X, A, P); DWORD dwMinMod = qwMod; for (DWORD dwI = 0; dwI < B-A; dwI++) { qwMod = (qwMod*X) % P; dwMinMod = min(dwMinMod, (DWORD)qwMod); if (dwMinMod == 1) { break; } } printf("%d\n", dwMinMod); return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - あまり |
User | yeye |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 4050 Byte |
Status | AC |
Exec Time | 2622 ms |
Memory | 384 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
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 | 7 ms | 256 KB |
sample_04.txt | AC | 1 ms | 256 KB |
subtask1_00.txt | AC | 1018 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 | 3 ms | 384 KB |
subtask1_09.txt | AC | 2 ms | 256 KB |
subtask1_10.txt | AC | 1 ms | 256 KB |
subtask1_11.txt | AC | 556 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 | 604 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 | 2622 ms | 256 KB |