POI2008 Lights

POI
高精度

POI2008 Lights

题目大意：

对于一个长度为n的数列p，数列中任意两个数字都互质，准备一个无限长的储存器，然后从p1开始，把储存器中p1的倍数位置都赋值为p1，把储存器中p2的倍数位置都赋值为p2，把储存器中p3……把储存器中pn的倍数全都赋值为pn。求最后每一个pi在储存器中出现的比例。用分数表示。

题解：

由于后面的数会把前面的数覆盖掉，我们不妨从后往前算：

很容易得到：

$$ ans _i = ( 1- \sum _ {j=i+1}^n ans _ j ) \times \frac 1 {p _i}$$

经过化简，可以得到一个递推式：

$$ ans _i = ans _ {i+1} \times \frac {p _{i+1}-1} {p _i}$$

这样就可以轻松的得到答案了。

数据范围非常大，我们要使用高精度算法。

但我们发现，我们不能直接写高精乘法、高精度的gcd以及高精除法。

因为显然会TLE。我们发现我们只需要求一个高精度数与一个低精度数之间的运算。

如此一来，题目即可解。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1005;
struct BigInt{
	static const int BASE=(int)1e9;
	ll num[N],len;
	BigInt(){
		len=1;
		memset(num,0,sizeof(num));
	}
	void maintain() {
        len=N;
        while(len-1>=1&&!num[len-1])len--;
    }
	BigInt& operator = (const int &tmp){
		len=1,num[0]=tmp;
		return *this;
	}
	bool operator ==(const int &tmp)const{
		if(len==1&&num[0]==tmp)return true;
		return false;
	}
	BigInt& operator *= (const int &tmp){
		for(int i=0;i<len;i++)
			num[i]=num[i]*tmp;
		for(int i=0;i<len;i++){
			if(num[i]>=BASE){
				num[i+1]+=num[i]/BASE;
				num[i]%=BASE;
			}
		}
		if(num[len])len++;
		return *this;
	}
	BigInt& operator /= (const int &tmp){
		ll rest=0;
		for(int i=len-1;i>=0;i--){
			num[i]+=rest*BASE;
			rest=num[i]%tmp;
			num[i]/=tmp;
		}
		maintain();
		return *this;
	}
	BigInt operator - (const BigInt &tmp)const{
		BigInt res;
		res.len=len;
		for(int i=0;i<len;i++){
			res.num[i]=num[i]-tmp.num[i];
			if(res.num[i]<0){
				res.num[i+1]--;
				res.num[i]+=BASE;
			}
		}
		res.maintain();
		return res;
	}
	int operator % (const int &tmp)const{
		BigInt t=*this;
		t/=tmp;
		t*=tmp;
		t=*this-t;
		return t.num[0];
	}
	void Print(){
		printf("%d",num[len-1]);
		for(int i=len-2;i>=0;i--)printf("%09d",num[i]);
	}
}son,mom;
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
struct Frac{
	BigInt son,mom;
	void Print(){
		son.Print();
		putchar('/');
		mom.Print();
		putchar('\n');
	}
	Frac operator * (const Frac &tmp)const{
		Frac res=(Frac){son,mom};
		int tson=tmp.son.num[0],tmom=tmp.mom.num[0],a,b;
		a=gcd(tmom,res.son%tmom);
		b=gcd(tson,res.mom%tson);
		res.son*=tson,res.mom*=tmom;
		res.son/=a,res.son/=b;
		res.mom/=a,res.mom/=b;
		return res;
	}
}ans[N];
int n,p[N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&p[i]);
	son=1,mom=p[n];
	ans[n]=(Frac){son,mom};
	for(int i=n-1;i>=1;i--){
		son=p[i+1]-1,mom=p[i];
		if(son==0||ans[i+1].son==0){
			son=0,mom=1;
			ans[i]=(Frac){son,mom};
		}else{
			int g=gcd(p[i+1]-1,p[i]);
			son/=g,mom/=g;
			ans[i]=ans[i+1]*(Frac){son,mom};
		}
	}
	for(int i=1;i<=n;i++)ans[i].Print();
	return 0;
}
分享到 评论