自动搬运

查看原文

来自洛谷，原作者为

	Star_F 嘟嘟嘟

搬运于2025-08-24 22:49:46，当前版本为作者最后更新于2023-09-02 10:54:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意：

有一个数值 $x$ 初值等于 $1$，每过 $a$ 小时乘以 $2$，每过 $b$ 小时除以 $2$，求操作 $k$ 小时后 $x$ 对 $998244353$ 取模的值。

题目分析：

对 $x$ 乘以 $2$ 不会发生错误，而对 $x$ 除以 $2$ 可能会发生精度错误，所以 根据同余定理：$\dfrac{a}{2} \equiv a \times 499122177 \pmod {998244353}$，即在对 $998244353$ 取模的情况下，可以用 $a \times 499122177$ 代替 $a \div 2$。

本体还是有一些细节的，如果只按照题目描述模拟会 WA。

Code:

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
#define end cout<<endl;
#define en cout<<" ";
#define LL long long
#define U unsigned
using namespace std;
template<class T>
inline void read(T &a){ register U LL x=0,t=1; register char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') t=-1; ch=getchar();} while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } a=x*t;}
inline void print(LL x){if(x<0)putchar('-'),x=-x;if(x>9) print(x/10);putchar(x%10+'0');}
void sovle(){
	long long ans=1,a,b,k;
	read(a);read(b);read(k);    //读入数据
	for(int i=1;i<=k;i++){
		if(i%a==0){         //每过去 a 小时
			ans*=2;			//乘以2并对998244353取模
			ans%=998244353;
		} 
		if(i%b==0&&ans>1){		//每过去 b 小时
			ans*=499122177;	//同余定理，除以2可以看作乘以499122177
			ans%=998244353;	//对998244353取模
		}
	}
	print(ans);			//输出答案
}

signed main(){
    sovle();
 	return 0;
}