Submit Info #209

Problem Lang User Status Time Memory
Sum of Floor of Linear cpp (anonymous) AC 71 ms 1.85 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
random_00 AC 19 ms 0.92 MiB
random_01 AC 71 ms 1.85 MiB
random_02 AC 58 ms 1.55 MiB
random_03 AC 41 ms 1.22 MiB
random_04 AC 19 ms 0.88 MiB
small_00 AC 14 ms 0.81 MiB
small_01 AC 36 ms 1.05 MiB
small_02 AC 28 ms 0.92 MiB
small_03 AC 18 ms 0.80 MiB
small_04 AC 12 ms 0.74 MiB

#include<bits/stdc++.h> using namespace std; long long lattice_points_under_line(long a,long b,long m,long n){ //return number of lattice points under (a/m)x+(b/m) long long res=0; while(true){ long long ar=a%m,br=b%m; long long aq=a/m,bq=b/m; res+=aq*(n-1)*n/2+bq*n; if(ar==0) break; long long na=m,nb=n*ar-m*((ar*(n-1)+br)/m)+br,nm=ar; n=(ar*(n-1)+br)/m; a=na;b=nb;m=nm; } return res; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while(t--){ long long n,m,a,b; cin >> n >> m >> a >> b; cout << lattice_points_under_line(a,b,m,n) << "\n"; } return 0; }