浪起网站建设,找别人做网站要考虑哪些,seo培训优化课程,建设通app免费版title : 暨南大学2023东软教育杯ACM校赛 题解 tags : ACM,练习记录 date : 2023-3-26 author : Linno 文章目录暨南大学2023东软教育杯ACM校赛 题解A-小王的魔法B-苏神的遗憾C-神父的碟D-基站建设E-小王的数字F-Uziの真身G-电子围棋H-二分大法I-丁真的小马朋友们J-单车运营K-超…
title : 暨南大学2023东软教育杯ACM校赛 题解 tags : ACM,练习记录 date : 2023-3-26 author : Linno 文章目录暨南大学2023东软教育杯ACM校赛 题解A-小王的魔法B-苏神的遗憾C-神父的碟D-基站建设E-小王的数字F-Uziの真身G-电子围棋H-二分大法I-丁真的小马朋友们J-单车运营K-超导铁轨L-承太郎的替身数暨南大学2023东软教育杯ACM校赛 题解
题目链接https://ac.nowcoder.com/acm/contest/47948
出题数量12/12 ,AK了
出题顺序A-B-C-D-F-G-J-E-I-H-L-K
简评首先感谢出题组手下留情再来点中等水平思维题估计就能搞死我了。因为题出的都比较板所以顺理成章地AK了打搅了大家的做题兴致非常抱歉这一场如果板子带够了并且刷题量达到一定水平打得都不会差的。如果觉得自己打得不好那希望这篇题解能给你带来帮助不懂也可以继续问喜欢ACM的话就请继续加油吧
A-小王的魔法
选某一个数它的因数都会被选中因此选它本身肯定是最优的那么我们直观觉得从大到小枚举的时候把因数都打上标签然后没打标签的数统计到答案里面就必然是正确的。但可惜n有1e18这样做肯定超时因此我们继续考虑更直观的结论
当i⌊n2⌋i\lfloor\frac{n}{2}\rfloori⌊2n⌋时显然有iii的所有因数都包含在2∗i2*i2∗i的所有因数中因此不必考虑对于i∈[n2,n]i\in [\frac{n}{2},n]i∈[2n,n]没有倍数能够将其包含所以是最优的因此答案就是⌈n2⌉\lceil\frac{n}{2}\rceil⌈2n⌉。
void solve(){int n;cinn;cout(n1)/2\n;
}B-苏神的遗憾
注意读题苏神是可以第一的但是成绩不能并列。因此一般情况下苏神的成绩是第二名成绩-1秒但是如果那是第一名的成绩就要跑得比这个更快一秒才行了。
void solve(){cinn;for(int i1;in;i) cina[i];stable_sort(a1,a1n);if(a[1]1a[2]) ansa[1]-1;else ansa[2]-1;coutans\n;
}C-神父的碟
前置知识中国剩余定理
原题意也就是让我们解同余方程组 {x≡b1moda1x≡b2moda2...x≡bnmodan\begin{cases} x\equiv b_1 \mod a_1 \\ x\equiv b_2 \mod a_2 \\ ...\\ x\equiv b_n \mod a_n \\ \end{cases} ⎩⎨⎧x≡b1moda1x≡b2moda2...x≡bnmodan 由于aaa两两互质令x(N/ai)∗yx(N/a_i)*yx(N/ai)∗y方程组等同于解同余方程(N/ai)y≡1modai(N/a_i)y\equiv 1 \mod a_i(N/ai)y≡1modai得到特解yiy_iyi则方程组的解为x0b1x1b2x2...brxrmodNx_0b_1x_1b_2x_2...b_rx_r \mod Nx0b1x1b2x2...brxrmodN,在模N意义下唯一。 注意到准备的箱子数aia_iai肯定是不同的质数也就是说不需要用到扩展CRT直接套板子即可。
#includebits/stdc.h
#define int long long
using namespace std;
const int N20;
int n,a[N],b[N],m[N],t[N],M1;inline int exgcd(int a,int b,int x,int y){if(!b){x1;y0;return a;}int dexgcd(b,a%b,y,x);y-a/b*x;return d;
}inline int inv(int a,int b){int d,x,y;dexgcd(a,b,x,y);return (x0)?(xb):x;
}void solve(){cinn;for(int i1;in;i){cina[i]b[i];M*a[i]; }int ans0;for(int i1;in;i){m[i]M/a[i];t[i]inv(m[i],a[i]);ansb[i]*m[i]%M*t[i]%M;ans%M; }coutans\n;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T1;while(T--){solve(); }return 0;
}D-基站建设
题目给定x,bx,bx,b我们可以转化为每个节点的做右端点[l,r][l,r][l,r]并且按照rrr从小到大排序每次贪心地选最右点建基站并跳过已被覆盖掉的节点即可保证最优。
#includebits/stdc.h
#define int long long
using namespace std;
const int N1e57;struct E{int l,r;bool operator (const E B)const{return rB.r;}
}s[N];void solve(){int n;cinn;for(int i1,x,b;in;i){cinxb;s[i].lx-b;s[i].rxb;}stable_sort(s1,s1n);int lst-0x3f3f3f3f,ans0;for(int i1;in;i){if(lsts[i].l){lsts[i].r;ans;}}coutans\n;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T1;while(T--){solve(); }return 0;
}E-小王的数字
前置知识数位DP
数位DP板题形式一般都如下给定L,R,问[L,R]范围内有多少XXX的数数据范围可出到1e18给定L,R,问[L,R]范围内有多少XXX的数数据范围可出到1e18给定L,R,问[L,R]范围内有多少XXX的数数据范围可出到1e18。
流程大概就是按位拆分给的数然后再按位记忆化搜索统计答案。代码细节各位自己看吧,dfs(stp,zero,lim,mx,now)表示搜到第stp位数最多连续mx位6当前连续了now位6时的状态zero是前置0标签lim是最高位标签。
#includebits/stdc.h
#define int long long
using namespace std;
const int N66;int len0,num[N],vis[N][N][N];int dfs(int stp,bool zero,bool lim,int mx,int now){if(!stp) return (mx3);if(!zero!limvis[stp][mx][now]) return vis[stp][mx][now];int jlim?num[stp]:9,ans0;for(int i0;ij;i){int tmp(i6)?now1:0;ansdfs(stp-1,zero(i0),lim(inum[stp]),max(mx,tmp),tmp);}if(!zero!lim) vis[stp][mx][now]ans;return ans;
}int solve(int x){len0;memset(vis,0,sizeof(vis));while(x){num[len]x%10;x/10;}return dfs(len,1,1,0,0);
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int L,R;cinLR;coutsolve(R)-solve(L-1)\n;return 0;
}
/*
1 1000000000000000000
*/ F-Uziの真身
看大家的代码写的都好短我开数组记了前缀和和后缀和。然后枚举‘z’的位置每个位置对答案的贡献就是前面‘j’的数量乘上后面‘h’的数量记得取模。
#includebits/stdc.h
#define int long long
using namespace std;
const int mod998244353;
const int N2e67;
int len;
string str;int numj[N],numh[N];void solve(){cinlen;cinstr;int ans0;numj[0](str[0]j);numh[len]0;for(int i1;ilen;i){numj[i]numj[i-1](str[i]j);}for(int ilen-1;i0;--i){numh[i]numh[i1](str[i]h);}
// for(int i0;ilen;i) coutnumj[i] numh[i] !!\n;for(int i1;ilen;i){if(str[i]z) ansnumj[i-1]*numh[i1]%mod,ans%mod;
// couti ans !!\n; }coutans\n;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T1;while(T--){solve(); }return 0;
}/*
14
mjbajzhmuaxing
9
jzhjzhjzh
*/G-电子围棋
爆搜就行了首先把最外面一圈全变成1然后剩下里面的就直接全变成6最后统计答案即可。
#includebits/stdc.h
#define int long long
using namespace std;
const int N55;int n,vis[N][N],mp[N][N];
int xx[]{0,0,-1,1},yy[]{-1,1,0,0};bool check(int x,int y){return (x1xny1yn!vis[x][y]mp[x][y]0);}inline void dfs(int x,int y,int id){mp[x][y]id;vis[x][y]1;for(int d0;d4;d){int nxxxx[d],nyyyy[d];if(check(nx,ny)) dfs(nx,ny,id);}
}void solve(){cinn;for(int i1;in;i){for(int j1;jn;j) cinmp[i][j];}for(int i1;in;i){if(!vis[i][1]mp[i][1]0) dfs(i,1,1);if(!vis[i][n]mp[i][n]0) dfs(i,n,1);if(!vis[n][i]mp[n][i]0) dfs(n,i,1); if(!vis[1][i]mp[1][i]0) dfs(1,i,1);}for(int i1;in;i){for(int j1;jn;j){if(!vis[i][j]mp[i][j]0) dfs(i,j,6);}}int ans0;for(int i1;in;i){for(int j1;jn;j){if(mp[i][j]6) ans; }}coutans\n;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T1;while(T--){solve(); }return 0;
}H-二分大法
没想到这题居然是暴力……大家可以忽略我的做法去看别人的。题目如果不保证所有i累加小于1e7的话可以考虑建平衡树我用的是FHQ Treap。这种数据结构可以很方便地进行序列的拆分和合并操作。然后对于拆分之后的两颗平衡树每个节点都有加法标签和乘法标签仿照线段树的pushdown操作进行先乘后加的处理即可。可能场内没有想我一样写平衡树的同学吧……pushdown真的很坑让我wa了两发。
#includebits/stdc.h
#define int long long
using namespace std;
const int N2e57;
const int mod1000000007;inline int read(){int x0,f1;char chgetchar();while(ch0||ch9){if(ch-) ff*-1;chgetchar();}while(ch0ch9) xx*10ch-0,chgetchar();return x*f;
}int n,q,a[N];
int ch[N][2],val[N],pri[N],sz[N],tg1[N],tg2[N],cnt,rt;void update(int x){sz[x]1sz[ch[x][0]]sz[ch[x][1]];
}
#define mid ((lr)1)
#define ls (ch[x][0])
#define rs (ch[x][1])
void pushdown(int x){if(xtg2[x]!1){if(ls){val[ls]val[ls]*tg2[x]%mod;tg1[ls]tg1[ls]*tg2[x]%mod;tg2[ls]tg2[ls]*tg2[x]%mod; }if(rs){val[rs]val[rs]*tg2[x]%mod;tg1[rs]tg1[rs]*tg2[x]%mod;tg2[rs]tg2[rs]*tg2[x]%mod; }tg2[x]1;}if(xtg1[x]){if(ls) val[ls](val[ls]tg1[x])%mod,tg1[ls](tg1[ls]tg1[x])%mod;if(rs) val[rs](val[rs]tg1[x])%mod,tg1[rs](tg1[rs]tg1[x])%mod;tg1[x]0;}
}int new_node(int v){sz[cnt]1;tg1[cnt]0;tg2[cnt]1;val[cnt]v;pri[cnt]rand();return cnt;
}int merge(int x,int y){if(!x||!y) return xy;pushdown(x);pushdown(y);if(pri[x]pri[y]){ch[x][1]merge(ch[x][1],y);update(x);return x;}else{ch[y][0]merge(x,ch[y][0]);update(y);return y;}
}void split(int now,int k,int x,int y){if(!now) xy0;else{pushdown(now);if(ksz[ch[now][0]]) ynow,split(ch[now][0],k,x,ch[now][0]);else xnow,split(ch[now][1],k-sz[ch[now][0]]-1,ch[now][1],y);update(now);}
}int build(int l,int r){if(lr) return 0;int nownew_node(a[mid]);
// coutl r a[mid] !!\n; ch[now][0]build(l,mid-1);ch[now][1]build(mid1,r);update(now);return now;
}void dfs(int x){if(!x) return;pushdown(x);dfs(ls);printf(%lld ,val[x]%mod);dfs(rs);
}signed main(){ srand(time(0));nread();for(int i1;in;i) a[i]read()%mod;rtbuild(1,n);qread();for(int i1,x,op,y,a,b;iq;i){xread();opread();yread();split(rt,x,a,b);if(op1) val[a](val[a]y)%mod,tg1[a](tg1[a]y)%mod;else val[a]val[a]*y%mod,tg2[a]tg2[a]*y%mod;rtmerge(b,a);}dfs(rt);puts();
}/*
7
1 2 3 4 5 6 7
3
3 1 7
2 1 1
1 2 24
2 5 4 3
04
2 5 4 3
3
1 2 2
3 1 3
1 2 5
——8 7 6 203
0 5 4
3
2 2 5
2 2 3
3 1 7 */I-丁真的小马朋友们
前置知识线段树
首先要想到一个很直观的结论就是我们每次都只选择长度为2的区间可以保证答案是最大的。因此我们只需要维护相邻两项的乘积即可。题目转化为了区间查询最大值和单点修改学过数据结构的同学可以快速通过。
#includebits/stdc.h
#define int long long
using namespace std;
const int N2e57;#define ls (p1)
#define rs (p1|1)
#define mid ((lr)1)
int n,k,a[N],b[N],mx[N2];void build(int p,int l,int r){if(lr){mx[p]b[l];return;}build(ls,l,mid);build(rs,mid1,r);mx[p]max(mx[ls],mx[rs]);
}void update(int p,int l,int r,int ql,int qr,int k){if(qllrqr){mx[p]k;return;}if(qlmid) update(ls,l,mid,ql,qr,k);if(qrmid) update(rs,mid1,r,ql,qr,k);mx[p]max(mx[ls],mx[rs]);
}int query(int p,int l,int r,int ql,int qr){if(qllrqr) return mx[p];int res0;if(qlmid) resquery(ls,l,mid,ql,qr);if(qrmid) resmax(res,query(rs,mid1,r,ql,qr));return res;
}void solve(){cinn;for(int i1;in;i) cina[i];for(int i1;in;i) b[i]a[i]*a[i1];b[n]b[n-1];build(1,1,n);cink;for(int i1,op,l,r;ik;i){cinoplr;if(op1){b[l]b[l]/a[l]*r;if(l1) b[l-1]b[l-1]/a[l]*r; if(ln) b[n-1]b[n]; else if(ln-1) b[n]b[n-1];a[l]r;update(1,1,n,n-1,n-1,b[n-1]); update(1,1,n,n,n,b[n]);update(1,1,n,l,l,b[l]);if(l1) update(1,1,n,l-1,l-1,b[l-1]);}else{coutquery(1,1,n,l,r-1)\n;}}
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T1;while(T--){solve(); }return 0;
}
/*
5
1 2 3 4 5
4
2 1 2
2 1 3
2 4 5
2 3 55
1 2 5 3 4
4
2 1 2
2 1 3
2 4 5
2 3 56
2 8 9 1 11 3
6
2 1 5
2 1 3
1 1 10
2 1 2
2 2 3
2 1 36
2 8 9 1 11 3
7
2 1 5
2 1 3
1 6 10
2 1 6
2 5 6
2 4 5
2 4 6
*/J-单车运营
前置知识图论基础知识最小费用最大流
最大流是在一个有向图中从S到T中间有许多节点每条边权限制了流量问单位时间能流过的最大流量是多少的模型。而最小费用最大流流是在这基础上给出每条边每流过一单位水流的费用问在最大流量的基础上最小费用的模型。显然题目可以套入这个模型从源点S到每个地点之间的最大流量便是单车最开始的摆放量aia_iai,不造成费用每两个地点之间的流量无限即可以不限量的搬运但是需要造成的费用便是两地的距离disijdis_{ij}disij每个地点到汇点的流量便是最终要摆放的车辆bib_ibi,也不造成费用。这样在满足摆放好车辆的前提下最大流所需要的努力最少最小费用。模型是怎么做到这一点的去学前置知识。
#includebits/stdc.h
#define int long long
#define inf 0x7f7f7f7f
using namespace std;
const int N305,M2e57; inline int read(){int x0,f1;char chgetchar();while(ch0||ch9){if(ch-) ff*-1;chgetchar();}while(ch0ch9) xx*10ch-0,chgetchar();return x*f;
}inline void write(int x){if(x9) write(x/10);putchar(x%100);
}int v[M],nxt[M],f[M],cnt1;
int flow[N],w[M],head[N];inline void addedge(int x,int y,int z,int k){cnt;v[cnt]y;w[cnt]z;f[cnt]k;nxt[cnt]head[x];head[x]cnt;cnt;v[cnt]x;w[cnt]0;f[cnt]-k;nxt[cnt]head[y];head[y]cnt;
}int n,m,S,T;
int dis[N],mcost,mflow;
int inq[N],pre[N];
int mp[N][N],tot0,q[M*10];inline bool spfa(){for(int iS;iT;i) dis[i]inf,inq[i]0;int L1,R1;q[L]S;inq[S]1;dis[S]0;flow[S]inf;while(LR){int froq[L];L;inq[fro]0;for(int ihead[fro];i;inxt[i]){if(w[i]dis[v[i]]dis[fro]f[i]){dis[v[i]]dis[fro]f[i];flow[v[i]]min(flow[fro],w[i]);pre[v[i]]i;if(!inq[v[i]]){q[R]v[i];inq[v[i]]1;}}} }return dis[T]!inf;
}inline void update(){int xT;while(x!S){int ipre[x];w[i]-flow[T];w[i^1]flow[T];xv[i^1];}mflowflow[T];mcostflow[T]*dis[T];
}void EK(){while(spfa()) update();
}void solve(){nread();S0;Tn1; for(int i1;in;i) addedge(S,i,read(),0);for(int i1;in;i) addedge(i,T,read(),0);for(int i1;in;i){for(int j1;jn;j){mp[i][j]read();addedge(i,j,inf,mp[i][j]);}}EK();write(mcost);
}signed main(){int T1;while(T--){solve(); }return 0;
}K-超导铁轨
前置知识SAM后缀自动机
因为被选中的位置不可用所对于两个字符串S,T来说都可以分段处理。也就是说S的每一段与T的每一段两两匹配求最长公共子串的最大长度。显然两两匹配会超时我们不妨对S的每一段字符串建广义SAM然后枚举T的每一段在SAM上跑最长匹配长度。别问我SAM是怎么做到的其实就是在DAG上一个一个字符去匹配如果匹配失败就像KMP一样跳转到Fail的位置去学前置知识。听说大佬用后缀数组被卡了可惜。
#includebits/stdc.h
using namespace std;
const int N2e67;int a[N],b[N],lst,tot1,rt1,num,ans0;
int fa[N],len[N],ch[N][30],sz[N][12];
char s[N];
vectorintG[N];
vectorstrings1,s2;
string str1,str2;void insert(int c,int id){ int plst,nplsttot;len[np]len[p]1,sz[np][id];while(p!ch[p][c]) ch[p][c]np,pfa[p];if(!p) fa[np]rt;else{int qch[p][c];if(len[q]len[p]1) fa[np]q;else{int nqtot;memcpy(ch[nq],ch[q],sizeof(ch[q]));len[nq]len[p]1,fa[nq]fa[q],fa[q]fa[np]nq;while(ch[p][c]q) ch[p][c]nq,pfa[p];}}
}void dfs(int x){int lenG[x].size();for(int i0;ilen;i){int yG[x][i];dfs(y);for(int id1;idnum;id) sz[x][id]sz[y][id];}
}bool check(int p){ if(!p) return false;for(int i1;inum;i){if(sz[p][i]) return true;}return false;
}void work(string s){int prt,l0;for(int i0;is.length();i){int cs[i]-a;if(check(ch[p][c])) l,pch[p][c];else{while(p!check(ch[p][c])) pfa[p];if(p) llen[p]1,pch[p][c];else l0,prt;}ansmax(ans,l);}
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinstr1str2;int l1str1.length(),l2str2.length(),n,m;memset(a,-1,sizeof(a)); memset(b,-1,sizeof(b));cinn;for(int i1;in;i) cina[i];cinm;for(int i1;im;i) cinb[i];stable_sort(a1,a1n);stable_sort(b1,b1m);
// string tmp;for(int i0,j1;il1;i){if(ia[j]){if(tmp!) s1.emplace_back(tmp);j;tmp;}else tmp.push_back(str1[i]);}if(tmp!) s1.emplace_back(tmp);tmp;for(int i0,j1;il2;i){if(ib[j]){if(tmp!) s2.emplace_back(tmp);j;tmp;}else tmp.push_back(str2[i]);}if(tmp!) s2.emplace_back(tmp);
// for(auto s:s1){lstrt;num;// couts !!\n;for(int i0;is.length();i) insert(s[i]-a,num);}for(int i2;itot;i) G[fa[i]].emplace_back(i);dfs(rt);for(auto s:s2){ work(s);// couts ans !!\n;}coutans\n;return 0;
} /*
aabaabaab
aa
3
3 6 9
0abcdabcdbacbd
bcd
1
4
1
1*/L-承太郎的替身数
前置知识数论分块迪利克雷卷积莫比乌斯反演
下面是推导过程如果有不懂的私信我或者去看前置知识。
题意转化为求∑i1S1∑j1S2lcm(i,j)\sum_{i1}^{S1}\sum_{j1}^{S2}lcm(i,j)∑i1S1∑j1S2lcm(i,j)最小公倍数lcm(i,j)i∗jgcd(i,j)lcm(i,j)\frac{i*j}{gcd(i,j)}lcm(i,j)gcd(i,j)i∗j 原式等于∑i1n∑j1mi⋅jgcd(i,j)∑d1nd⋅∑i1⌊nd⌋∑j1⌊md⌋[gcd(i,j)1]i⋅j∑d1n∑d∣in∑d∣jmμ(d)⋅i⋅j令g(n,m)∑i1n∑j1mi⋅jn⋅(n1)2×m⋅(m1)2sum(n,m)∑d1nμ(d)⋅d2⋅g(⌊nd⌋,⌊md⌋)原式∑d1nd⋅sum(⌊nd⌋,⌊md⌋),可用数论分块和线性筛解决。原式等于 \sum_{i1}^n\sum_{j1}^m\frac{i\cdot j}{\gcd(i,j)} \\ \sum_{d1}^n d\cdot\sum_{i1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)1]\ i\cdot j \\ \sum_{d1}^n\sum_{d\mid i}^n\sum_{d\mid j}^m\mu(d)\cdot i\cdot j\\ 令 g(n,m)\sum_{i1}^n\sum_{j1}^m i\cdot j\frac{n\cdot(n1)}{2}\times\frac{m\cdot(m1)}{2} \\ \operatorname{sum}(n,m)\sum_{d1}^n\mu(d)\cdot d^2\cdot g(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor) \\ 原式\sum_{d1}^n d\cdot\operatorname{sum}(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor) ,可用数论分块和线性筛解决。 原式等于i1∑nj1∑mgcd(i,j)i⋅jd1∑nd⋅i1∑⌊dn⌋j1∑⌊dm⌋[gcd(i,j)1] i⋅jd1∑nd∣i∑nd∣j∑mμ(d)⋅i⋅j令g(n,m)i1∑nj1∑mi⋅j2n⋅(n1)×2m⋅(m1)sum(n,m)d1∑nμ(d)⋅d2⋅g(⌊dn⌋,⌊dm⌋)原式d1∑nd⋅sum(⌊dn⌋,⌊dm⌋),可用数论分块和线性筛解决。
#includebits/stdc.h
#define int long long
using namespace std;
const int mod1e97;
const int N1e77;int np[N],pri[N],mu[N],sum[N],cnt0;
void init(){mu[1]np[1]1;for(int i2;iN;i){if(!np[i]) pri[cnt]i,mu[i]-1;for(int j1;jcntpri[j]*iN;j){np[pri[j]*i]1;if(i%pri[j]) mu[i*pri[j]]-mu[i];else break;}}for(int i1;iN;i) sum[i](sum[i-1]i*i%mod*(mu[i]mod)%mod)%mod;
} int Sum(int x,int y){return (x*(x1)/2%mod)*(y*(y1)/2%mod)%mod;
}int func(int x,int y){int res0;for(int l1,r;lmin(x,y);lr1){rmin(x/(x/l),y/(y/l));res(res(sum[r]-sum[l-1]mod)*Sum(x/l,y/l)%mod)%mod;}return res;
}int Solve(int x,int y){int res0;for(int l1,r;lmin(x,y);lr1){rmin(x/(x/l),y/(y/l));res(res(r-l1)*(lr)/2%mod*func(x/l,y/l)%mod)%mod;}return res;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);init();int t,n,m;cint;while(t--){cinnm;coutSolve(n,m)\n; }return 0;
}
/*
2
4 5
4 5
*/
