QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#610967#7033. Resistors in Parallelucup-team4906#AC ✓4ms3640kbC++202.1kb2024-10-04 18:20:202024-10-04 18:20:21

Judging History

你现在查看的是最新测评结果

  • [2024-10-04 18:20:21]
  • 评测
  • 测评结果:AC
  • 用时:4ms
  • 内存:3640kb
  • [2024-10-04 18:20:20]
  • 提交

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