题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1128
题意：对于一个长度为 n 的数列 p，数列中任意两个数互质。准备一个无限长的储存器。然后从 p1 开始，把储存器中 p1 倍数位置都赋值为 p1，把储存器中 p2 倍数位置都赋值为 p2，把储存器中 p3 倍数位置都赋值为 p3。把储存器中 pn 倍数位置都赋值为 pn。最后求每个 pi 在储存器中出现的比例，用分数表示。
这种覆盖的问题一般倒着考虑，即\(A_i=A_{i+1} \cdot \frac {P_{i+1}-1}{P_i}\)
高精度维护分数即可，考虑到暴力求 gcd 太麻烦了，实际上我们只需要求分子和\(P_i\) 的 gcd，维护一个高精度取低精模即可。
|
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 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 1010 #define MAX_LEN 10000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int bit=1000000000; const int W=9; struct big { int len; ll x[MAX_LEN]; ll& operator [](int a) {return x[a];} friend void operator *=(big &a,int b) { int len=a.len; for(int i=1;i<=len;i++)a[i]*=b; int now=1; while(now<=len) { if(a[now]>=bit)a[now+1]+=a[now]/bit,a[now]%=bit; if(now==len&&a[len+1])len++; now++; } a.len=len; } friend void operator /=(big &a,int b) { int len=a.len; for(int i=len;i>=1;i--) { a[i-1]+=a[i]%b*bit; a[i]/=b; } while(len&&a[len]==0)len--; a.len=len; } friend int operator %(big a,int b) { int ret=0; for(int i=a.len;i>=1;i--) ret=((ll)ret*bit+a[i])%b; return ret; } void set(int k) { len=1; x[1]=k; } void print() { for(int i=len;i>=1;i--) if(i==len)printf("%d",x[i]); else printf("%09d",x[i]); } }up,down,ans_up[N],ans_down[N]; int gcd(int a,int b) {return b==0?a:gcd(b,a%b);} int n,p[N]; int main() { n=read(); for(int i=1;i<=n;i++)p[i]=read(); up.set(1),down.set(1); for(int i=n;i>=1;i--) { int G=gcd(p[i],up%p[i]); up/=G,down*=p[i]/G; ans_up[i]=up,ans_down[i]=down; if(p[i]==1) { while(--i) { ans_up[i].set(0); ans_down[i].set(1); } } else G=gcd(p[i]-1,down%(p[i]-1)),up*=(p[i]-1)/G,down/=G; } for(int i=1;i<=n;i++) { ans_up[i].print(); putchar('/'); ans_down[i].print(); putchar('\n'); } } |
Comments | NOTHING