Submit Info #1026

Problem Lang User Status Time Memory
Sum of Floor of Linear cpp chocorusk AC 67 ms 1.87 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
random_00 AC 17 ms 0.92 MiB
random_01 AC 67 ms 1.87 MiB
random_02 AC 44 ms 1.52 MiB
random_03 AC 40 ms 1.23 MiB
random_04 AC 18 ms 0.89 MiB
small_00 AC 11 ms 0.67 MiB
small_01 AC 36 ms 1.05 MiB
small_02 AC 27 ms 0.92 MiB
small_03 AC 19 ms 0.80 MiB
small_04 AC 11 ms 0.71 MiB

#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; ll Sum_of_Floor_of_Linear(ll n, ll m, ll a, ll b){ if(n==0) return 0; ll ret=0; if(a>=m){ ret+=n*(n-1)/2*(a/m); a%=m; } if(b>=m){ ret+=n*(b/m); b%=m; } if(a==0) return ret; ll q=(a*n+b)/m, r=(a*n+b)%m; ret+=q*(r/a); ret+=Sum_of_Floor_of_Linear(q, a, m, r%a); return ret; } int main() { int t; scanf("%d", &t); for(int i=0; i<t; i++){ ll n, m, a, b; scanf("%lld %lld %lld %lld", &n, &m, &a, &b); printf("%lld\n", Sum_of_Floor_of_Linear(n, m, a, b)); } return 0; }