QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#610967 | #7033. Resistors in Parallel | ucup-team4906# | AC ✓ | 4ms | 3640kb | C++20 | 2.1kb | 2024-10-04 18:20:20 | 2024-10-04 18:20:21 |
Judging History
answer
#include<bits/stdc++.h>
#define F(i, a, b) for(int i = a; i <= b; i ++)
using namespace std;
const int M = 1e4 + 10;
vector<int>pri;
bool vst[M];
vector<int>n;
vector<int> operator * (const vector<int>a, int b)
{
int m = a.size(); vector<int>c(m);
for (int i = 0; i < m; i ++)c[i] = a[i] * b;
for (int i = 0; i < m - 1; i ++)
{
c[i + 1] += c[i] / 10;
c[i] %= 10;
}
while (c[m - 1] >= 10) {c.push_back(c[m - 1] / 10); c[m - 1] %= 10; m ++;}
return c;
}
bool operator > (const vector<int>b, const vector<int>a)
{
int n = a.size(), m = b.size();
if (n > m) return 0;
if (n < m) return 1;
for (int i = n - 1; i >= 0; i --)
{
if (a[i] < b[i]) return 1;
if (a[i] > b[i]) return 0;
}
return 0;
}
void pre(int n)
{
for (int i = 2; i <= n; i ++)
{
if (!vst[i]) {pri.push_back(i);}
for (int x : pri)
{
if (1LL * i * x > n) break;
vst[i * x] = 1;
if (i % x == 0)break;
}
}
}
void sol()
{
string s;
cin >> s;
int len = s.length();
for (int i = len - 1; i >= 0; i --)n.push_back(s[i] - '0');
vector<int>v = {1};
multiset<int>a, b;
for (int x : pri)
{
vector<int>tv = v * x;
if (tv > n) break;
v = tv;
a.insert(x); b.insert(x + 1);
}
vector<int>g;
for (int x : a)
{
for (int y : b)
{
if (y % x == 0)
{
g.push_back(x);
b.erase(b.find(y)); b.insert(y / x);
break;
}
}
}
for (int x : g)a.erase(x);
vector<int>ta = {1}, tb = {1};
for (int x : a) ta = ta * x;
for (int y : b) tb = tb * y;
int p = ta.size(), q = tb.size();
for (int i = p - 1; i >= 0; i --) cout << ta[i];
cout << '/';
for (int i = q - 1; i >= 0; i --) cout << tb[i];
cout << '\n';
n.clear();
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
pre(10000);
int t; cin >> t;
F(i, 1, t) sol();
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3640kb
input:
3 10 100 1000
output:
1/2 5/12 35/96
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
100 9055 764034929998350 175478445981 3066144 373717 79921483664325743 31787974933 19712134724867403 86665280597 9459527960934 45840 6831794283 631941163719 8241229170655 992693590670671467 288745916793799209 83790620689711 21805764718032208 5455 39 909 3 79423683 43 198853556983437047 5221603522064...
output:
385/1152 76253198879/321052999680 30808063/119439360 12155/41472 715/2304 298080686527/1284211998720 30808063/119439360 298080686527/1284211998720 30808063/119439360 1859834119/7644119040 715/2304 30808063/119439360 955049953/3822059520 1859834119/7644119040 14009792266769/61642175938560 29808068652...
result:
ok 100 lines
Test #3:
score: 0
Accepted
time: 2ms
memory: 3592kb
input:
100 179305586963 96883378626478880429056246520023290774722301848230232935789122 161758308595898 178124354133226622987953243895918403851 1893414732443742551436 61239961784411409687653066831224920774024514762604245 2305567963945518424753102147331756069 619035744750559608675 8749921888120 4072968059924...
output:
30808063/119439360 1749936537208721528520879643954955339690231858377/9753327077118246544899138751790948391321600000000 1859834119/7644119040 2694014995838881344684929537/13636826284246500397547520000 742518990138757/3328677500682240 47269280380971678953725754621107734221741/2546294662990352585865481...
result:
ok 100 lines
Test #4:
score: 0
Accepted
time: 4ms
memory: 3544kb
input:
100 22939325522365660014467787481973310847349569760706025172732597301326936494429523296729661721 7029461483963351683658343686551075543421117918728658657046178242960651103186293515 33800318667247027732146374420765580419884087620966241732522617435712471851616225196963088465984970 242755330487870550410...
output:
154395010617978451305968882287268454695382683719518660706078042712504201/920479896805919917804276884737662765142862669596588016402432000000000000 16811536080563707769953565248128113493150676390734314896696553/97952070308873397595155186362822686508099250929270784000000000 8597794956283366017875489147...
result:
ok 100 lines