U369821 【FYOI-R1】Spasmodic

本题是签到题，没有头图，但是有形式化题意。

小 $\texttt{F}$ 和小 $\texttt{Y}$ 正在卷题目。 小 $\texttt{F}$ 和小 $\texttt{Y}$ 的题单里最初分别有 $n$ 个和 $m$ 个题目。两人轮流卷题，他们的水平不下上下，所以每次可以任选一个人的题单卷 $f(x,y)$ 个题目，其中 $x,y$ 分别表示小 $\texttt{F}$ 和小 $\texttt{Y}$ 的题单里剩下的题目数量。卷完的题目会从对应题单上消失。最后无题可卷的人输掉卷题游戏。 $f(x,y)$ 定义如下： $$ f(x,y)=\left\{ \begin{aligned} \operatorname{gcd}(x,y), && xy>0 \\ x+y, && xy=0 \end{aligned} \right. $$ 由于小 $\texttt{Y}$ 请小 $\texttt{F}$ 吃了 $2000$ 元的饭而小 $\texttt{F}$ 回请了 $4000$ 元，小 $\texttt{F}$ 取得了先手。他想问问你，在他和小 $\texttt{Y}$ 均选择最优策略的情况下，他能否获胜并赢得 “大卷批” 称号？ 然而小 $\texttt{F}$ 觉得这题太简单了。他决定让你求出对于 $\forall i\in [1,n]$，$\forall j\in [1,m]$，有多少组 $(i,j)$ 可以使他获胜。答案对 $993244853$ 取模。如果你不能在 $1$ 秒内给出答案，他就会感到不削，并把你从创新班里踢出去。 ------------ ### 形式化题意 定义 $f(x,y)$ 如下： 两个数 $a,b$ 开始时满足 $a=x,b=y$，两人轮流对 $a$ 或 $b$ 减去 $\operatorname{gcd}(a,b)$，操作后需满足 $a\ge0,b\ge0$，操作后出现 $a=b=0$ 的局面则获胜。若先手有必胜策略则 $f(x,y)=1$，否则 $f(x,y)=0$。 给定 $n,m$，求 $\sum_{i=1}^{n}\sum_{j=1}^{m}f(i,j)\operatorname{mod} 993244853$。 特别地，$\operatorname{gcd}(a,0)=a$，$\operatorname{gcd}(0,b)=b$。 ------------ **请选手使用较快的读入输出方式。**

本题每个测试点有多组数据。 第 $1$ 行一个整数 $T$，表示数据组数。 接下来 $T$ 行，第 $i$ 行两个整数 $n,m$，含义与题目描述中相同。

输出 $T$ 行，第 $i$ 行为第 $i$ 组数据对应的答案。

**本题采用捆绑测试。** 对于 $100\%$ 的数据，$1\le T\le 10^5$，$1\le n,m\le 10^{16}$。 $$ \def\arraystretch{1.3} \begin{array}{|c|c|c|c|c|} \hline \textbf{Subtask} & \textsf{分值} & {T\le} & {n,m\le} & \text{Level} \cr\hline 1 & 10 & 50 & 50 & 0\cr\hline 2 & 10 & 500 & 10^3 & 7\cr\hline 3 & 20 & 500 & 10^6 & 12\cr\hline 4 & 20 & 2\times10^3 & 10^{10} & 15\cr\hline 5 & 40 & 10^5 & 10^{16} & 16\cr\hline \end{array} $$