ACM训练日记—2月7日

啥也不说了，整理下题目吧。

1，牛客网（常州大学新生寒假训练会试）G题零下e度

给出一个n，求最接近(n!)/e的整数。 n<=1e8

这道题目刚开始上来就感觉是斯特林公式，可求了半天因为浮点数不能求逆元和精度的问题无法求，后来想了许多办法，就是没觉得泰勒公式能做，因为如果用泰勒公式展开1/e的话，就要求到n，也就是说复杂度是O(n)，可我一直觉得C++1秒跑八百万，1e8的数明显超时，可这结果还真是啪啪打脸，估计是牛客网放的数据没那么大。这么看来这道题还真是水，模拟一遍e^x泰勒展开乘入n!取模就做出来了。

从这道题我也该好好反省对C++1s处理800万过于钻牛角尖。还是太菜了，感觉做题时一直思路打不开，自己给自己设置了许多思维障碍，真是好不甘心啊。

2，BSGS算法

主要就是求a^x=b(mod c)，(c是素数)，已知a,b,c，求满足条件的最小x。

以下来自：https://www.cnblogs.com/yuiffy/p/3877381.html

A^x=B(mod C)(C是质数)，都是整数，已知A、B、C求x。
先把x=i*m+j，其中m=ceil(sqrt(C))，（ceil是向上取整）。
这样原式就变为A^(i*m+j)=B(mod C)，
再变为A^j=B*A^(-m*i) (mod C)，
先循环j=0~(C-1)，把（A^j,j)加入hash表中，这个就是Baby Steps（现在可以播放Baby Steps-Varsity了）。
下面我们要做的是枚举等号右边，从hash表中找看看有没有，有的话就得到了一组i j，x=i*m+j，得到的这个就是正确解。
所以，接下来要解决的就是枚举B*A^(-m*i) (mod C)这一步（这就是Giant Step，快放Giant Step-Astronauts(May'n・椎名慶治)）。
A^(-m*i)相当于1/(A^(m*i))，里面有除法，在mod里不能直接用除法，这时候我们就要求逆元。

其实关于哈希表我只是点不够还不大懂，这种方法应用的比较少，原理也比较好懂。（此法哈希表降低复杂度sqrt(n)）

3，拓展BSGS算法

以下来自：http://tonyfang.is-programmer.com/posts/178997.html

一开始的方程为 Ax×a+C×b=B(a,b为整数)

那么设t=gcd(A,C)，显然，B如果不能被t整除，就无解了。

下面来看个方程：

(At)x′×a′+(Ct)×b′=Bt

两端乘t，得到Ax′+1×a′+C×b′=B

那么我们就有办法了，算x′，然后算x=x′+1即可。

继续迭代直至gcd(A,C)=1，假设做了cnt次，那么x=x′+cnt。

理解起来并不难，但是我还是不太懂哈希表。。。所以保存一个模版

const int maxn = 65535;
struct hash
{
int a,b,next;
} Hash[maxn << 1];
int flg[maxn + 66];
int top,idx;
void ins(int a,int b)
{
int k = b & maxn;
if(flg[k] != idx)
{
flg[k] = idx;
Hash[k].next = -1;
Hash[k].a = a;
Hash[k].b = b;
return ;
}
while(Hash[k].next != -1)
{
if(Hash[k].b == b) return ;
k = Hash[k].next;
}
Hash[k].next = ++ top;
Hash[top].next = -1;
Hash[top].a = a;
Hash[top].b = b;
}
int find(int b)
{
int k = b & maxn;
if(flg[k] != idx) return -1;
while(k != -1)
{
if(Hash[k].b == b) return Hash[k].a;
k = Hash[k].next;
}
return -1;
}
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int ext_gcd(int a,int b,int& x,int& y)
{
int t,ret;
if (!b)
{
x=1,y=0;
return a;
}
ret=ext_gcd(b,a%b,x,y);
t=x,x=y,y=t-a/b*y;
return ret;
}
int Inval(int a,int b,int n)
{
int x,y,e;
ext_gcd(a,n,x,y);
e=(LL)x*b%n;
return e<0?e+n:e;
}
int pow_mod(LL a,int b,int c)
{
LL ret=1%c;
a%=c;
while(b)
{
if(b&1)ret=ret*a%c;
a=a*a%c;
b>>=1;
}
return ret;
}
int BabyStep(int A,int B,int C)
{
top = maxn;
++ idx;
LL buf=1%C,D=buf,K;
int i,d=0,tmp;
for(i=0; i<=100; buf=buf*A%C,++i)if(buf==B)return i;
while((tmp=gcd(A,C))!=1)
{
if(B%tmp)return -1;
++d;
C/=tmp;
B/=tmp;
D=D*A/tmp%C;
}
int M=(int)ceil(sqrt((double)C));
for(buf=1%C,i=0; i<=M; buf=buf*A%C,++i)ins(i,buf);
for(i=0,K=pow_mod((LL)A,M,C); i<=M; D=D*K%C,++i)
{
tmp=Inval((int)D,B,C);
int w ;
if(tmp>=0&&(w = find(tmp)) != -1)return i*M+w+d;
}
return -1;
}
int main()
{
int a,b,c;
while(~scanf("%d%d%d",&a,&c,&b)&&a&&b&&c)//a^x=b(mod c)....求最小的x、、1<=a,b,c<=1e9
{
int temp = BabyStep(a,b,c);
if(temp<0||b>=c)
printf("Orz,I can’t find D!\n");
else
printf("%d\n",temp);
}
return 0;
}

秒客网

ACM训练日记—2月7日

相关文章