結果
問題 | No.1918 Simple Math ? |
ユーザー |
👑 ![]() |
提出日時 | 2022-04-29 22:05:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 190 ms / 2,000 ms |
コード長 | 2,105 bytes |
コンパイル時間 | 2,066 ms |
コンパイル使用メモリ | 197,200 KB |
最終ジャッジ日時 | 2025-01-28 22:54:22 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>#pragma GCC optimize("Ofast")#define _GLIBCXX_DEBUGusing namespace std;using std::cout;using std::cin;using std::endl;using ll=long long;using ld=long double;ll ILL=2167167167167167167;const int INF=2100000000;const ll mod=1e9+7;#define rep(i,a) for (ll i=0;i<a;i++)#define all(p) p.begin(),p.end()template<class T> using _pq = priority_queue<T, vector<T>, greater<T>>;template<class T> ll LB(vector<T> &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();}template<class T> ll UB(vector<T> &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();}template<class T> bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}else return 0;}template<class T> bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}else return 0;}template<class T> void So(vector<T> &v) {sort(v.begin(),v.end());}template<class T> void Sore(vector<T> &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});}void yneos(bool a){if(a) cout<<"Yes\n"; else cout<<"No\n";}template<class T> void vec_out(vector<T> &p){for(int i=0;i<(int)(p.size());i++){if(i) cout<<" ";cout<<p[i];}cout<<"\n";}ll jyo(ll x,ll y,ll z){ll H=y; //ここからll a=1,b=(x%z+z)%z,c=1;while(H>0){a*=2;if(H%a!=0){H-=a/2;c*=b;c%=z;}b*=b;b%=z;} //ここまでreturn c;}ll f(ll a){ll tmp=sqrt(a)-2;while(true){if(tmp*tmp>a) return tmp-1;tmp++;}}void solve();// oddloopint main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t=1;cin>>t;rep(i,t) solve();}void solve(){ll a,n;cin>>a>>n;ll upp=f(a*n);vector<ll> p(a);rep(i,a){p[i]=(i*i)%a;if(p[i]==0) p[i]=a;}ll ans=(upp*(upp+1))%mod;ans=(ans*((2*upp+1)%mod))%mod;ans=(ans*jyo(6,mod-2,mod))%mod;ans%=mod;//cout<<upp<<" "<<ans<<"\n";//if(a<100) vec_out(p);rep(i,a){if(i<(upp+1)%a) ans=(ans-p[i])%mod;ans=(ans-p[i]*(((1+upp)/a)%mod))%mod;}ans+=p[0];ans%=mod;//cout<<ans<<"\n";ans=(ans*jyo(a,mod-2,mod))%mod;ans=(((n%mod)*upp)%mod-ans)%mod;cout<<(ans+mod)%mod<<"\n";}