P9577题解

Star_F · 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;
}