제출 #1184576

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1184576		windowwife	마술쇼 (APIO24_show)	C++20	100 / 100	8 ms	8580 KiB

Alice

#ifndef rtgsp
#include "Alice.h"
#endif // rtgsp

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e6 + 4;

#ifdef rtgsp
ll setN (int n)
{
    ll x;
    cin >> x;
    return x;
}
#endif // rtgsp

int n;
vector<pair<int, int>> Alice()
{
    n = 5000;
    ll x = setN(n);
    vector<pair<int, int>> v;
    v.clear();
    for (int i = 2; i <= n; i++)
        v.push_back({x % (i - 1) + 1, i});
    return v;
}

#ifdef rtgsp
int main ()
{
    freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    vector<pair<int, int>> v = Alice();
    for (pair<int, int> p : v) cout << p.first << " " << p.second << '\n';
}
#endif // rtgsp

Bob

#ifndef rtgsp
#include "Bob.h"
#endif // rtgsp

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e6 + 4;
int min_prime[maxn], primes[maxn], mod[maxn], cnt = 0;

void sieve()
{
    for (int i = 2; i < maxn; i++)
    {
        if (min_prime[i] == 0)
        {
            min_prime[i] = i;
            primes[++cnt] = i;
            mod[i] = -1;
        }
        for (int j = 1; i * primes[j] < maxn; j++)
        {
            min_prime[i * primes[j]] = primes[j];
            if (min_prime[i] == primes[j]) break;
        }
    }
}
ll inv_mod (__int128 x, int mod)
{
    int p = mod - 2;
    x %= mod;
    ll res = 1;
    for (; p > 0; p >>= 1)
    {
        if (p & 1) res = res * x % mod;
        x = x * x % mod;
    }
    return res;
}
void print (__int128 x)
{
    string s;
    while (x != 0)
    {
        s.push_back((x % 10) + '0');
        x /= 10;
    }
    reverse(s.begin(), s.end());
    cout << s;
}
ll Bob(vector<pair<int, int>> v)
{
    ll mx = 0, ans = 0;
    __int128 res = 0, cur = 1;
    sieve();
    for (pair<int, int> p : v)
    {
        p.first--; p.second--;
        while (p.second != 1)
        {
            mod[min_prime[p.second]] = p.first % min_prime[p.second];
            p.second /= min_prime[p.second];
        }
    }
    for (int i = 1; i <= cnt; i++)
    {
        if (mod[primes[i]] == -1) continue;
        if (cur > 1e18)
        {
            mx = i - 1;
            break;
        }
        else cur *= primes[i];
    }
    for (int i = 1; i <= mx; i++)
    {
        if (mod[primes[i]] == -1) continue;
        __int128 mi = cur/primes[i];
        ll ni = inv_mod(mi, primes[i]);
        res = (res + mod[primes[i]]*mi%cur*ni%cur)%cur;
    }
    ans = res;
    return ans;
}

#ifdef rtgsp
int main ()
{
    freopen(task".OUT", "r", stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n = 5000, x, y;
    vector<pair<int, int>> v;
    v.clear();
    for (int i = 1; i <= (n - 2)/2; i++)
    {
        cin >> x >> y;
        v.push_back({x, y});
    }
    cout << Bob(v);
}
#endif // rtgsp

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65