BZOJ 1128 [POI2008]Lam 高精度

题意:链接方法:高精度解析:N<=1000,P<=10^9首先因为所有数都互质。并且后来者可以覆盖。所以倒着搞拿样例来说5->1/53->1/5 * 4/32->4/15 * 2/2所以然后因为数据范围问题，所以需要上高精。高精除gcd的时候，千万别傻不啦叽写高精对高精那种除2流的GCD，，别以为这是log(n)这特么是log(10^1000)直接变成O(n^3)，想过？没门。所以转化成高精对低精的gcd就好。也就是说我们写个高精模低精就可以了。代码:#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define N 1100#define M 1000000000using namespace std;typedef long long ll;int n;struct node{ll num[1010];int len;}ans[N][2];node dec(node &a,node &b){node ret;memset(ret.num,0,sizeof(ret.num));int len=a.len;for(int i=1;i<=len;i++){ret.num[i]+=a.num[i]-b.num[i];if(ret.num[i]<0){ret.num[i]+=M;ret.num[i+1]–;}}while(ret.num[len]==0&&len>1)len–;ret.len=len;return ret;}node mul(node &a,ll x){if(x==1)return a;node ret;memset(ret.num,0,sizeof(ret.num));int len=a.len;for(int i=1;i<=len;i++){ret.num[i]+=a.num[i]*x;ret.num[i+1]+=ret.num[i]/M;ret.num[i]%=M;}while(ret.num[len+1]){len++;ret.num[len+1]+=ret.num[len]/M;ret.num[len]%=M;}ret.len=len;return ret;}void div(node &a,ll x){if(x==1)return;int len=a.len;ll lll=0;for(int i=len;i>=1;i–){lll=lll*M+a.num[i];a.num[i]=lll/x;lll=lll%x;}while(a.num[len]==0&&len>1)len–;a.len=len;}bool cmp(node &a,node &b){if(a.len>b.len)return 1;;else{int len=a.len;while(len){if(a.num[len]>b.num[len])return 1;;len–;}return 1;}}ll get_yu(node &a,ll b){ll lll=0;int len=a.len;for(int i=len;i>=1;i–){lll=lll*M+a.num[i];a.num[i]=lll/b;lll=lll%b;}return lll;}ll gcd(ll a,ll b){while(b){ll t=b;b=a%b;a=t;}return a;}ll gcd(node a,ll b){return gcd(b,get_yu(a,b));}ll p[N],pp[N];void print(node &a,node &b){printf(“%lld”,a.num[a.len]);for(int i=a.len-1;i>=1;i–)printf(“%09lld”,a.num[i]);printf(“/”);printf(“%lld”,b.num[b.len]);for(int i=b.len-1;i>=1;i–)printf(“%09lld”,b.num[i]);puts(“”);}int main(){scanf(“%d”,&n);for(int i=1;i<=n;i++)scanf(“%lld”,&p[i]),pp[i]=p[i]-1;ans[n][0].num[1]=1,ans[n][0].len=1;ans[n][1].num[1]=p[n],ans[n][1].len=1;if(ans[n][1].num[1]==M)ans[n][1].num[1]=0,ans[n][1].num[2]=1,ans[n][1].len++;int flag=0;if(p[n]==1)flag=1;for(int i=n-1;i>=1;i–){if(flag){ans[i][0].len=ans[i][1].len=ans[i][1].num[1]=1;continue;}ll tmp3=gcd(p[i],pp[i+1]);ll tmp1=gcd(ans[i+1][0],p[i]/tmp3),tmp2=gcd(ans[i+1][1],pp[i+1]/tmp3);ans[i][0]=mul(ans[i+1][0],pp[i+1]/(tmp2*tmp3)),ans[i][1]=mul(ans[i+1][1],p[i]/(tmp1*tmp3));div(ans[i][0],tmp1),div(ans[i][1],tmp2);if(p[i]==1)flag=1;}for(int i=1;i<=n;i++){print(ans[i][0],ans[i][1]);}}

生活比你想象的要容易得多，只要学会接受那些不可接受的，