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

题目链接

https://www.luogu.org/problemnew/show/P2044

题解

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

  • \(x_1 = (ax+c) \mod m\)
  • \(x_2 = (ax_1+c) \mod m = (a^{2}x+ac+c) \mod m\)
  • \(x_3 = (ax_2+c) \mod m = (a^{3}x+a^{2}c+ac+c) \mod m\)
  • \(\ldots\)
  • \(x_n = (a^{n}x+a^{n-1}c+ \ldots + ac+c) \mod 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;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注