結果
問題 | No.1918 Simple Math ? |
ユーザー | logx |
提出日時 | 2022-04-29 22:54:14 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,522 ms / 2,000 ms |
コード長 | 3,006 bytes |
コンパイル時間 | 1,978 ms |
コンパイル使用メモリ | 203,764 KB |
実行使用メモリ | 4,384 KB |
最終ジャッジ日時 | 2023-09-11 14:20:15 |
合計ジャッジ時間 | 21,841 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 154 ms
4,380 KB |
testcase_01 | AC | 9 ms
4,384 KB |
testcase_02 | AC | 9 ms
4,376 KB |
testcase_03 | AC | 7 ms
4,384 KB |
testcase_04 | AC | 12 ms
4,376 KB |
testcase_05 | AC | 10 ms
4,376 KB |
testcase_06 | AC | 161 ms
4,380 KB |
testcase_07 | AC | 236 ms
4,380 KB |
testcase_08 | AC | 122 ms
4,380 KB |
testcase_09 | AC | 64 ms
4,376 KB |
testcase_10 | AC | 158 ms
4,380 KB |
testcase_11 | AC | 14 ms
4,384 KB |
testcase_12 | AC | 212 ms
4,380 KB |
testcase_13 | AC | 139 ms
4,380 KB |
testcase_14 | AC | 88 ms
4,380 KB |
testcase_15 | AC | 38 ms
4,380 KB |
testcase_16 | AC | 658 ms
4,380 KB |
testcase_17 | AC | 713 ms
4,380 KB |
testcase_18 | AC | 964 ms
4,380 KB |
testcase_19 | AC | 1,032 ms
4,380 KB |
testcase_20 | AC | 856 ms
4,380 KB |
testcase_21 | AC | 1,468 ms
4,376 KB |
testcase_22 | AC | 1,451 ms
4,376 KB |
testcase_23 | AC | 1,439 ms
4,380 KB |
testcase_24 | AC | 1,428 ms
4,376 KB |
testcase_25 | AC | 1,435 ms
4,380 KB |
testcase_26 | AC | 1,522 ms
4,380 KB |
testcase_27 | AC | 1,513 ms
4,380 KB |
testcase_28 | AC | 891 ms
4,380 KB |
testcase_29 | AC | 2 ms
4,380 KB |
testcase_30 | AC | 1 ms
4,380 KB |
testcase_31 | AC | 1,505 ms
4,376 KB |
testcase_32 | AC | 2 ms
4,380 KB |
testcase_33 | AC | 2 ms
4,380 KB |
ソースコード
#ifdef LOGX #define _GLIBCXX_DEBUG #endif #include <bits/stdc++.h> using namespace std; #include <atcoder/modint> using namespace atcoder; using mint=modint1000000007; /*---------macro---------*/ #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rep2(i, s, n) for (int i = s; i < (int)(n); i++) #define unless(x) if(!(x)) #define until(x) while(!(x)) #define ALL(a) a.begin(),a.end() #define RALL(a) a.rbegin(),a.rend() #define mybit(i,j) (((i)>>(j))&1) /*---------type/const---------*/ constexpr int big=1000000007; //constexpr int big=998244353; constexpr double EPS=1e-8; //適宜変える typedef long long ll; typedef unsigned long long ull; typedef std::string::const_iterator state; //構文解析 constexpr int dx[4]={1,0,-1,0}; constexpr int dy[4]={0,1,0,-1}; constexpr char newl='\n'; struct{ constexpr operator int(){return -int(1e9)-10;} constexpr operator ll(){return -ll(1e18)-10;} }neginf; struct{ constexpr operator int(){return int(1e9)+10;} constexpr operator ll(){return ll(1e18)+10;} constexpr auto operator -(){return neginf;} }inf; /*---------debug---------*/ #ifdef LOGX #include <template/debug.hpp> #else #define dbg(...) ; #define dbgnewl ; #define prt(x) ; #define _prt(x) ; #endif /*---------function---------*/ template<typename T> T max(const std::vector<T> &a){T ans=a[0];for(T elem:a){ans=max(ans,elem);}return ans;} template<typename T> T min(const std::vector<T> &a){T ans=a[0];for(T elem:a){ans=min(ans,elem);}return ans;} template<typename T,typename U> bool chmin(T &a,const U b){if(a>b){a=b;return true;}return false;} template<typename T,typename U> bool chmax(T &a,const U b){if(a<b){a=b;return true;}return false;} bool valid(int i,int j,int h,int w){return (i>=0 && j>=0 && i<h && j<w);} template<class T,class U>T expm(T x,U y,const ll mod=big){T res=1;while(y){if(y&1)(res*=x)%=mod;(x*=x)%=mod;y>>=1;}return res;} template<class T,class U>T exp(T x,U y){T res=1;while(y){if(y&1)res*=x;x*=x;y>>=1;}return res;} ll mysqrt(ll v){ ll ok=1; ll ng=sqrt(v)*3; while(ng-ok>1){ ll mid=(ok+ng)/2; (mid*mid<=v ? ok:ng)=mid; } return ok; } mint solve(){ ll a,n; cin >> a >> n; mint ans=0; const ll X=mysqrt(a*n)-1; ans-=mint(X)*(X+1)*(2*X+1)/a/6; for(ll t=0;t<a;t++){ ll cnt=X/a+(t!=0 && t<=X%a); ans+=mint(t)*t/a*cnt; ans-=mint((t*t/a))*cnt; } ll a2=1; { ll da=a; for(ll i=2;i*i<=da;i++)if(da%i==0){ int cnt=0; while(da%i==0)da/=i,cnt++; rep(j,(cnt+1)/2)a2*=i; } if(da!=1)a2*=da; } ans+=X/a2; ans+=X*mint(((X+1)*(X+1)-1)/a); ans+=(X+1)*mint((a*n)/a - ((X+1)*(X+1)-1)/a); return ans; } int main(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout << std::fixed << std::setprecision(10); /*------------------------------------*/ int t; cin >> t; while(t--){ cout << solve().val() << newl; } }