[atARC148F]998244353 → 1000000007

标签：frac cdot atARC148F 1000000007 000 mul printf rm 998244353

科技题

蒙哥马利算法：求$a\cdot m^{-1}\ mod\ M$（其中$m^{-1}$为$m$模$M$的逆元）

记$t=a\cdot \frac{m\cdot m^{-1}-1}{M}\ mod\ m$，则$a+tM\equiv a(1+\frac{m\cdot m^{-1}-1}{M}\cdot M)\equiv 0(mod\ m)$

在此基础上，即有$a\cdot m^{-1}\equiv (a+tM)m^{-1}\equiv \frac{a+tM}{m}(mod\ M)$

 

记$f(a)=\frac{a+tM}{m}$，取$\begin{cases}m=998244353\\M=10^{9}+7\end{cases}$，即可用$6$次操作求出$f(a)$

${\rm rem}\ \ b\ \ a$

${\rm mul}\ \ b\ \ b\ \ \frac{m\cdot m^{-1}-1}{M}$

${\rm rem}\ \ b\ \ b$

${\rm mul}\ \ b\ \ b\ \ M$

${\rm add}\ \ b\ \ a\ \ b$

${\rm mul}\ \ a\ \ b\ \ m模2^{64}的逆元$

同时，有$f(a)\le \lfloor\frac{a+m(M-1)}{m}\rfloor=\lfloor\frac{a}{m}\rfloor+M-1$，则迭代$o(\log_{m}a)$次即可使$a\le M$

 

回到原问题，考虑如下操作——

${\rm mul}\ \ c\ \ a\ \ b$【$1,000,000,012,000,000,036$】

$c=f(c)$【$2,001,758,752$】

${\rm mul}\ \ c\ \ c\ \ (m^{4}\ mod\ M)$【$687,882,754,110,932,128$】

$c=f(c)$【$1,689,092,563$】

$c=f(c)$【$1,000,000,007$】

$c=f(c)$【$1,000,000,007$】

（每行后【】中的数为$c$的上界，估计方式参考前者）

若最终$c=M$，即存在$a$或$b$为$0$，而显然$f(0)=0$，结合过程与此矛盾

共需$4\times 6+2=26$次操作，可以通过

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef unsigned long long ull;
 4 const int m=998244353,M=1000000007,m4=343639189;
 5 const int m0=4924091,k=4915446;
 6 const ull m1=996491785301655553;
 7 void f(){
 8     printf("rem D C\n");
 9     printf("mul D D %d\n",k);
10     printf("rem D D\n");
11     printf("mul D D %d\n",M);
12     printf("add D C D\n");
13     printf("mul C D %llu\n",m1);
14 }
15 int main(){
16     printf("26\n");
17     printf("mul C A B\n");
18     f();
19     printf("mul C C %d\n",m4);
20     f(),f(),f();
21     return 0;
22 }

View Code

 

标签：frac,cdot,atARC148F,1000000007,000,mul,printf,rm,998244353
From： https://www.cnblogs.com/PYWBKTDA/p/16715271.html