QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#737495 | #9622. 有限小数 | Ashbourne | TL | 0ms | 3652kb | C++23 | 3.8kb | 2024-11-12 16:00:00 | 2024-11-12 16:00:01 |
Judging History
answer
%:pragma GCC optimize(2)
%:pragma GCC optimize("Ofast")
%:pragma GCC optimize("inline")
%:pragma GCC optimize("-fgcse")
%:pragma GCC optimize("-fgcse-lm")
%:pragma GCC optimize("-fipa-sra")
%:pragma GCC optimize("-ftree-pre")
%:pragma GCC optimize("-ftree-vrp")
%:pragma GCC optimize("-fpeephole2")
%:pragma GCC optimize("-ffast-math")
%:pragma GCC optimize("-fsched-spec")
%:pragma GCC optimize("unroll-loops")
%:pragma GCC optimize("-falign-jumps")
%:pragma GCC optimize("-falign-loops")
%:pragma GCC optimize("-falign-labels")
%:pragma GCC optimize("-fdevirtualize")
%:pragma GCC optimize("-fcaller-saves")
%:pragma GCC optimize("-fcrossjumping")
%:pragma GCC optimize("-fthread-jumps")
%:pragma GCC optimize("-funroll-loops")
%:pragma GCC optimize("-fwhole-program")
%:pragma GCC optimize("-freorder-blocks")
%:pragma GCC optimize("-fschedule-insns")
%:pragma GCC optimize("inline-functions")
%:pragma GCC optimize("-ftree-tail-merge")
%:pragma GCC optimize("-fschedule-insns2")
%:pragma GCC optimize("-fstrict-aliasing")
%:pragma GCC optimize("-fstrict-overflow")
%:pragma GCC optimize("-falign-functions")
%:pragma GCC optimize("-fcse-skip-blocks")
%:pragma GCC optimize("-fcse-follow-jumps")
%:pragma GCC optimize("-fsched-interblock")
%:pragma GCC optimize("-fpartial-inlining")
%:pragma GCC optimize("no-stack-protector")
%:pragma GCC optimize("-freorder-functions")
%:pragma GCC optimize("-findirect-inlining")
%:pragma GCC optimize("-fhoist-adjacent-loads")
%:pragma GCC optimize("-frerun-cse-after-loop")
%:pragma GCC optimize("inline-small-functions")
%:pragma GCC optimize("-finline-small-functions")
%:pragma GCC optimize("-ftree-switch-conversion")
%:pragma GCC optimize("-foptimize-sibling-calls")
%:pragma GCC optimize("-fexpensive-optimizations")
%:pragma GCC optimize("-funsafe-loop-optimizations")
%:pragma GCC optimize("inline-functions-called-once")
%:pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define rep(i, j, k) for(int i = j; i <= k; ++ i)
using namespace std;
int Mod;
const int INF = 1e9;
int tot = 0;
int pow5[35], po5 = 0, ydbs[255], po2 = 0, pow2[35];
int fpow(int a, int b){
int x = 1;
while(b){
if(b & 1) x = x * a % Mod;
a = a * a % Mod;
b >>= 1;
}
return x;
}
void solve(){
int a, b;
cin >> a >> b;
int t1 = 0, t2 = 0, t, x = 1, y = 1, z = 1;
while(b % 2 == 0){
t1++;
b /= 2;
x *= 2;
}
while(b % 5 == 0){
t2++;
b /= 5;
x *= 5;
}
if(b == 1){
cout << 0 << " " << 1 << endl;
return;
}
t = max(t1, t2);
for(int i = 1; i <= t; ++ i) y = y * 10;
z = y / x;
Mod = b;
int tt = b, phi = b;
rep(i, 2, sqrt(tt)){
if(tt % i == 0){
phi /= i;
phi *= (i - 1);
while(tt % i == 0) tt /= i;
}
}
if(tt){
phi /= tt;
phi *= (tt - 1);
}
int tar = a * z % Mod * fpow(y % Mod, phi - 1) % Mod;
tar = Mod - tar;
int minn = 1e9, mind = 1;
int SX = INF / b;
rep(i, 1, tot){
if(ydbs[i] > SX) break;
int tx = tar * ydbs[i] % Mod;
if(minn > tx){
minn = tx;
mind = ydbs[i];
}
if(minn == 1) break;
}
cout << minn << " " << mind * b << endl;
}
signed main(){
ios::sync_with_stdio(0);
pow5[0] = 1;
while(pow5[po5] <= INF) {
++po5;
pow5[po5] = pow5[po5 - 1] * 5;
}
po5--;
pow2[0] = 1;
while(pow2[po2] <= INF){
++po2;
pow2[po2] = pow2[po2 - 1] << 1;
}
po2 --;
int x = 1;
while(x <= INF){
rep(i, 0, po5){
if(x * pow5[i] > INF) break;
ydbs[++tot] = x * pow5[i];
}
x <<= 1;
}
sort(ydbs + 1, ydbs + tot + 1);
// cout << tot << endl;
int T;
cin >> T;
while(T--) solve();
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3652kb
input:
4 1 2 2 3 3 7 19 79
output:
0 1 1 3 1 14 3 316
result:
ok 4 case(s)
Test #2:
score: -100
Time Limit Exceeded
input:
10000 11 12 28 53 17 60 2 35 17 181 80 123 68 141 79 163 71 99 13 64 33 61 15 32 16 61 11 86 33 74 128 143 40 53 7 23 30 31 5 6 86 181 73 91 13 23 71 81 1 2 7 38 117 160 33 83 129 151 88 153 25 58 16 19 19 141 95 124 43 96 71 139 11 59 106 109 93 152 34 43 17 99 1 57 20 159 16 25 5 73 159 170 172 17...
output:
1 3 1 54272 1 6 1 7 1 231680000 23 3936 1 36096000 5 326 1 63360 0 1 1 31232 0 1 1 4880 1 10750 1 18500 1 11714560 1 331250 1 2944 1 31 1 6 1 289600000 1 455000 1 58880