bzoj-1128 Lam

题意：

给出一个长度为n的数列p，数列中数字两两互质；

有一个无限长的寄存器，现从p[1]开始，依次将其所有的倍数在寄存器中置为p[i]；

求最后每个数字所染色区域在寄存器中占比，用一个既约分数表示；

n<=1000，p[i]<=maxint；

题解：

这傻逼题我居然傻逼了一晚上；

说白了就是一个递推，f[i]=1/p[i] *Π(p[j]-1)/p[j]；

这坨东西多好推啊，要是这题输出浮点数多好；

然并卵，显然这东西乘个n次早就爆long long了；

于是要上高精度；

上高精度可不容易，这就要考虑考虑这个式子怎么求方便了；

显然Π(p[i]-1)/p[i]可以通过后缀积来搞搞，由最后面推过来；

每次只要分子分母同乘低精度就好；

而最后的f[i]也就是分母乘个p[i]的事；

然而并不能直接输出，因为题中要的是既约分数。。。

高精GCD+高精除高精？

开玩笑吧！我还能有那码力？

首先一个显然的事，如果a与c互质，b与c互质，那么a*b与c互质；

然后我们只需要将每次低精乘高精之前，对另一个高精求一下GCD；

然后低精与另一个高精除掉这个GCD，就依然保持分数为既约形式；

这样只需要低精与高精的GCD，和高精除低精了；

高精除低精不用说，况且还是保证整除；

GCD这我就逗了，被坑的去写了一个除二讨论的GCD；

这特么。。我居然以为高精度的log很小。。。

总复杂度O(n^2log(高精度))=O(n^3)四舍五入就是一个亿啊！

真是被逗的不轻，然后我就写了个√n的质因数分解。。

只要每次分出的质因数去判断高精度能不能除掉就好了；

直接加起来边模边算，反正都是同余系下；

然后这题就结束了，复杂度O(n^2√n)；

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 2100
#define M 1100
#define mod 10000
using namespace std;
typedef long long ll;
struct BIG
{
	int a[N],top;
	void print()
	{
		int i=top;
		printf("%d",a[i--]);
		while(i>=0)
			printf("%04d",a[i--]);
	}
	bool judge(int p)
	{
		int ret=0;
		for(int i=top;i>=0;i--)
		{
			ret=(ret*mod%p+a[i])%p;
		}
		return !ret;
	}
	friend bool operator ==(BIG &a,BIG &b)
	{
		memcpy(a.a,b.a,sizeof(int)*(b.top+1));
		a.top=b.top;
	}
	friend bool operator <(BIG &a,int b)
	{
		if(a.top>=3)	return 0;
		if(a.top==2)
			return (ll)a.a[2]*mod*mod+a.a[1]*mod+a.a[0]<b;
		if(a.top==1)
			return a.a[1]*mod+a.a[0]<b;
		if(a.top==0)
			return a.a[0]<b;
	}
	friend void operator -=(BIG &a,int b)
	{
		a.a[2]-=b/mod/mod;
		a.a[1]-=b/mod%mod;
		a.a[0]-=b%mod;
		while(a.a[a.top]==0&&a.top)
			a.top--;
	}
	friend void operator *=(BIG &b,int a)
	{
		static int i;
		ll index,up;
		for(i=0,up=0;i<=b.top;i++)
		{
			index=up+(ll)a*b.a[i];
			b.a[i]=index%mod;
			up=index/mod;
		}
		while(up)
			b.a[++b.top]=up%mod,
			up=up/mod;
	}
	friend void operator /=(BIG &a,int b)
	{
		static int i,up;
		static ll index;
		i=a.top,up=0;
		while(i>=0)
		{
			index=(ll)up*mod+a.a[i];
			a.a[i]=index/b;
			up=index%b;
			i--;
		}
		while(a.a[a.top]==0&&a.top)
			a.top--;
	}
	friend int gcd(int a,BIG &b)
	{
		static BIG temp;
		memcpy(temp.a,b.a,sizeof(int)*(b.top+1));
		temp.top=b.top;
		int ret=1;
		for(int i=2;i*i<=a;i++)
		{
			if(a%i==0)
			{
				while(a%i==0&&temp.judge(i))
				{
					a/=i;
					temp/=i;
					ret*=i;
				}
				while(a%i==0)
					a/=i;
			}
		}
		if(a!=1)
			if(temp.judge(a))
				ret*=a;
		return ret;
	}
}up[1100],down[1100];
int p[1100];
int main()
{
	int n,m,i,j,k;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",p+i);
	up[n+1].a[0]=down[n+1].a[0]=1;
	for(i=n;i>1;i--)
	{
		up[i]==up[i+1];
		down[i]==down[i+1];
		if(p[i]-1==0)
		{
			memset(up[i].a,0,sizeof(int)*(up[i].top+1));
			memset(down[i].a,0,sizeof(int)*(down[i].top+1));
			up[i].top=0;
			down[i].top=0;
			down[i].a[0]=1;
		}
		else
		{
			k=gcd(p[i]-1,down[i+1]);
			down[i]/=k;
			up[i]*=(p[i]-1)/k;
		}
		k=gcd(p[i],up[i]);
		up[i]/=k;
		down[i]*=p[i]/k;
	}
	for(i=2;i<=n+1;i++)
	{
		k=gcd(p[i-1],up[i]);
		up[i]/=k;
		down[i]*=p[i-1]/k;
	}
	for(i=2;i<=n+1;i++)
	{
		up[i].print();
		putchar('/');
		down[i].print();
		putchar('\n');
	}
	return 0;
}