Submission #18933254


Source Code Expand

Copy
#include <bits/stdc++.h>
#include <atcoder/all>
#define INF 1e9
#define INFLL 1ull<<60u
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;

using vi = vector<int>;
using vvi = vector<vi>;
using vpii = vector<pair<int,int>>;

// (a^n)%modを求めるライブラリ
long long modpow(long long a, long long n) {
    long long res = 1;
    static const int mod = 1e9+7;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

bool IsPrime(ll num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (ll i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}

//min(x,y)が0以下の場合はmax(x,y)が返される
//ユークリッドの互除法を元に実装
ll gcd(ll x,ll y){
    if(x<y) swap(x,y);
    //xの方が常に大きい
    ll r;
    while(y>0){
        r=x%y;
        x=y;
        y=r;
    }
    return x;
}


void solve() {
    int T; cin >> T;


    auto solve = []() -> int {
        int N,S,K; cin >> N >> S >> K;
        auto g = gcd(N,K);
        if (S % g) return  -1;
        N/=g; S/=g; K/=g;
        atcoder::modint::set_mod(N);
        auto x = -atcoder::modint(S) / K;
        return x.val();
    };
    while(T--) cout << solve() << endl;
}


int main() {
    solve();
    return 0;
}

Submission Info

Submission Time
Task E - Throne
User reud
Language C++ (GCC 9.2.1)
Score 500
Code Size 2036 Byte
Status AC
Exec Time 5 ms
Memory 3696 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 1
AC × 32
Set Name Test Cases
Sample sample_01.txt
All hand_01.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, sample_01.txt
Case Name Status Exec Time Memory
hand_01.txt AC 5 ms 3480 KB
random_01.txt AC 3 ms 3480 KB
random_02.txt AC 2 ms 3420 KB
random_03.txt AC 2 ms 3692 KB
random_04.txt AC 3 ms 3560 KB
random_05.txt AC 2 ms 3480 KB
random_06.txt AC 2 ms 3696 KB
random_07.txt AC 5 ms 3520 KB
random_08.txt AC 2 ms 3588 KB
random_09.txt AC 2 ms 3512 KB
random_10.txt AC 2 ms 3556 KB
random_11.txt AC 3 ms 3556 KB
random_12.txt AC 2 ms 3564 KB
random_13.txt AC 2 ms 3692 KB
random_14.txt AC 2 ms 3428 KB
random_15.txt AC 3 ms 3560 KB
random_16.txt AC 2 ms 3400 KB
random_17.txt AC 2 ms 3588 KB
random_18.txt AC 4 ms 3408 KB
random_19.txt AC 2 ms 3408 KB
random_20.txt AC 2 ms 3560 KB
random_21.txt AC 2 ms 3412 KB
random_22.txt AC 2 ms 3476 KB
random_23.txt AC 5 ms 3588 KB
random_24.txt AC 2 ms 3480 KB
random_25.txt AC 3 ms 3512 KB
random_26.txt AC 2 ms 3696 KB
random_27.txt AC 2 ms 3488 KB
random_28.txt AC 2 ms 3432 KB
random_29.txt AC 2 ms 3696 KB
random_30.txt AC 3 ms 3584 KB
sample_01.txt AC 2 ms 3400 KB