結果

問題 No.3307 Almost Equal
コンテスト
ユーザー GOTKAKO
提出日時 2025-11-19 03:12:37
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,596 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,214 ms
コンパイル使用メモリ 196,788 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-11-19 03:12:41
合計ジャッジ時間 3,932 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

__int128_t safemod(__int128_t a,__int128_t m){
    a %= m; a += m;
    return a>=m?a-m:a;
}
__int128_t floor(__int128_t a,__int128_t b){
    if(b < 0) a *= -1,b *= -1;
    return a<0?(a+1)/b-1:a/b; 
}
__int128_t ceil(__int128_t a,__int128_t b){
    if(b < 0) a *= -1,b *= -1;
    return a>0?(a-1)/b+1:a/b; 
}
__int128_t floorsum(__int128_t N,__int128_t M,__int128_t a,__int128_t b){
    //return Σ(i=0~N-1)floor((a*i+b)/M).
    __int128_t ret = 0;
    if(a >= M) ret += a/M*(N*(N-1)/2),a %= M;
    if(b >= M) ret += b/M*N,b %= M;
    __int128_t maxy = a*N+b;
    if(maxy >= M) ret += floorsum(maxy/M,a,M,maxy%M);
    return ret;
}
__int128_t floorsum2(__int128_t N,__int128_t M,__int128_t a,__int128_t b){
    if(N <= 0) return 0; //a < 0 or b < 0 or N <= 0;  
    __int128_t ret = 0;
    if(a < 0 || a >= M) ret += floor(a,M)*(N*(N-1)/2),a = safemod(a,M);
    if(b < 0 || b >= M) ret += floor(b,M)*N,b = safemod(b,M);
    __int128_t maxy = a*N+b;
    if(maxy >= M) ret += floorsum(maxy/M,a,M,maxy%M);
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long A,B,C,D; cin >> A >> B >> C >> D;
    __int128_t g = gcd(A,B);
    A /= g,B /= g;
    g = gcd(C,D);
    C /= g,D /= g;
    if(A == C && B == D){cout << "-1\n"; return 0;}
    if(A*D > C*B) swap(A,C),swap(B,D);

    __int128_t lcm = B*D,a = A*D,c = C*B;
    __int128_t n = (lcm+c-a-1)/(c-a);
    __int128_t answer = n;
    answer += floorsum(n,2*B,2*A,2*A+B);
    answer -= floorsum(n,2*D,2*C,2*C+D);
    cout << (long long)answer << endl;
}
0