結果
問題 | No.1918 Simple Math ? |
ユーザー |
![]() |
提出日時 | 2022-04-29 22:54:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,525 ms / 2,000 ms |
コード長 | 3,006 bytes |
コンパイル時間 | 2,109 ms |
コンパイル使用メモリ | 197,796 KB |
最終ジャッジ日時 | 2025-01-28 23:38:22 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
#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;}}