oj.uz

답안 #473872

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
473872 2021-09-16T10:57:53 Z HossamHero7 Euklid (COCI20_euklid) C++14
19 / 110
 1000 ms 71096 KB 
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef vector <ll> row;
typedef vector <row> matrix;
#define endl '\n'
#define fast ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define all(v) ((v).begin()), ((v).end())
#define allR(v) ((v).rbegin()), ((v).rend())
#define For(i,n) for(int i=0;i<(int)(n);i++)
#define sz(v) v.size()
#define swapS(a,b) if(a>b) swap(a,b)
const ll mod = 1e9+7;
const ll OO = 1e18;
const ll invalid = -1e18;
int dx[] = {0,0,-1,1,1,1,-1,-1};
int dy[] = {1,-1,0,0,1,-1,-1,1};
ll fixMod(ll x){
    return ((x%mod) + mod) % mod;
}
ll lcm(ll a,ll b){
    return max(a,b)/__gcd(a,b)*min(a,b);
}
ll power(ll a,ll b){
    if(b==0) return 1;
    if(b==1) return a;
    if(b&1){
        ll y=power(a,b/2);
        return (y*y*a);
    }
    else {
        ll y=power(a,b/2);
        return (y*y);
    }
}
ll inv(ll n){
    return power(n,(mod-2));
}
matrix zero(int n,int m){
    return matrix(n,row(m,0));
}
matrix identity(int n){
    matrix ret = zero(n,n);
    for(int i=0;i<n;i++){
        ret[i][i] = 1;
    }
    return ret;
}
matrix multiply(const matrix &a, const matrix &b){
    matrix ret = zero(a.size(),b[0].size());
    for(int i=0;i<a.size();i++){
        for(int k=0;k<a[0].size();k++){
            for(int j=0;j<b[0].size();j++){
                ret[i][j] += a[i][k] * b[k][j];
                ret[i][j] = ret[i][j];
            }
        }
    }
    return ret;
}
matrix matrixPower(matrix &a,ll b){
    if(b == 0) return identity(a.size());
    if(b == 1) return a;
    matrix r = matrixPower(a,b/2);
    if(b&1) return multiply(multiply(r,r),a);
    return multiply(r,r);
}
ll dp[3005][3005];
ll calc(int a,int b){
    ll &ret = dp[a][b];
    if(~ret) return ret;
    if(a<b) return ret = calc(b,a);
    if(a>=b && b > 1) return ret = calc(a/b,b);
    else return ret = a;
}
void solve(){
    ll g,h;
    cin>>g>>h;
    if(g == h){
        cout<<g<<" "<<h<<endl;
        return;
    }
    for(int i=1;i<=3000;i++){
        for(int j=1;j<=3000;j++){
            if(__gcd(i,j) == g && calc(i,j) == h){
                cout<<i<<" "<<j<<endl;
                return;
            }
        }
    }
}
int main()
{
    fast
    ll t=1;
    cin>>t;
    memset(dp,-1,sizeof(dp));
    while(t--){
        //Some important Notes:
        //  1- Any minus with mod fixed mod
        //  2- Any divide with mod inverse
        //  3- Any mod problem make mod in every where
        //  4- Any dp problem don't forget to return the saved value :)
        solve();
    }
    return 0;
}

Compilation message

euklid.cpp: In function 'matrix multiply(const matrix&, const matrix&)':
euklid.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i=0;i<a.size();i++){
      |                 ~^~~~~~~~~
euklid.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int k=0;k<a[0].size();k++){
      |                     ~^~~~~~~~~~~~
euklid.cpp:54:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             for(int j=0;j<b[0].size();j++){
      |                         ~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 70992 KB Output is correct
2 Correct 34 ms 70948 KB Output is correct
3 Correct 30 ms 70872 KB Output is correct
4 Correct 34 ms 70984 KB Output is correct
5 Correct 33 ms 70888 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 70976 KB Output is correct
2 Correct 475 ms 70976 KB Output is correct
3 Execution timed out 1087 ms 70896 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1031 ms 70964 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 70980 KB Output is correct
2 Correct 60 ms 70972 KB Output is correct
3 Correct 65 ms 70864 KB Output is correct
4 Correct 66 ms 70972 KB Output is correct
5 Correct 69 ms 70988 KB Output is correct
6 Correct 84 ms 70976 KB Output is correct
7 Correct 86 ms 70980 KB Output is correct
8 Correct 101 ms 71096 KB Output is correct
9 Correct 105 ms 70976 KB Output is correct
10 Correct 132 ms 70976 KB Output is correct

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 70980 KB Output is correct
2 Correct 60 ms 70972 KB Output is correct
3 Correct 65 ms 70864 KB Output is correct
4 Correct 66 ms 70972 KB Output is correct
5 Correct 69 ms 70988 KB Output is correct
6 Correct 84 ms 70976 KB Output is correct
7 Correct 86 ms 70980 KB Output is correct
8 Correct 101 ms 71096 KB Output is correct
9 Correct 105 ms 70976 KB Output is correct
10 Correct 132 ms 70976 KB Output is correct
11 Execution timed out 1077 ms 70892 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 70992 KB Output is correct
2 Correct 34 ms 70948 KB Output is correct
3 Correct 30 ms 70872 KB Output is correct
4 Correct 34 ms 70984 KB Output is correct
5 Correct 33 ms 70888 KB Output is correct
6 Correct 92 ms 70976 KB Output is correct
7 Correct 475 ms 70976 KB Output is correct
8 Execution timed out 1087 ms 70896 KB Time limit exceeded
9 Halted 0 ms 0 KB -