[洛谷 2044][NOI2012]随机数生成器

题目链接

https://www.luogu.org/problem/P2044

题解

我们先来算一下生成的 \(x_n\) 究竟是多少。（为了简单起见，下面把 \(x_0\) 简记为 \(x\)）

• \(x_1 = (ax+c) \bmod m\)
• \(x_2 = (ax_1+c) \bmod m = (a^{2}x+ac+c) \bmod m\)
• \(x_3 = (ax_2+c) \bmod m = (a^{3}x+a^{2}c+ac+c) \bmod m\)
• \(\ldots\)
• \(x_n = (a^{n}x+a^{n-1}c+ \ldots + ac+c) \bmod m\)

整个式子被分为两部分：\(a^{n}x\) 可以用快速幂解决。

而 \(a^{n-1}c+ \ldots + ac+c\) 这个等比数列也可以递归解决。

然而由于中间结果溢出的原因，我们需要使用龟速乘法来对 long long 取模。

#include <iostream>
using namespace std;
long long m,a,c,x,n,g;
long long smul(long long x,long long y)
{
 long long ans=0;
 while(y)
 {
  if(y&1)ans=(ans+x)%m;
  x=(x+x)%m;
  y>>=1;
 }
 return ans;
}
long long fpow(long long x,long long y)
{
 long long ans=1;
 while(y)
 {
  if(y&1)ans=smul(ans,x);
  x=smul(x,x);
  y>>=1;
 }
 return ans;
}
long long calc(long long n)
{
 if(n==1)return c;
 long long res=calc(n/2);
 res=(res+smul(res,fpow(a,n/2)))%m;
 if(n&1)res=(res+smul(fpow(a,n-1),c))%m;
 return res;
}
int main()
{
 cin>>m>>a>>c>>x>>n>>g;
 long long ans=smul(fpow(a,n),x);
 ans=(ans+calc(n))%m;
 cout<<ans%g<<endl;
 return 0;
}