[POJ 3101] | Eurce's Blog

分类里写的是扩展欧几里德，但完全用不到。倒是被高精度稍微卡了下。

题意是共有n个星体各以vi的速度绕同一中心公转，问所有星体排成一条直线的周期。

这里注意“排成一条直线”，可以是在圆周的一侧或是另一侧。这里可以取速度最快的星作为运动参照物，求其他星体相对该星的速度，并计算各星体(v0-vi)*x可同时被0.5除尽的最小倍数值x。x即为所求周期值。0.5是因为可在圆周的任意一侧。

用题意vi = 1/ti来表示的话，则1/t0 – 1/ti = (ti-t0) / (t0*ti)，那么取所有分母的lcm为nu，所有分子的gcd为de，则nu/(2*de)则是所求的x了。

思路出来之后，还有部分细节，首先就是去重，然后是计算素数表大小和估计高精度数组最大长度，最后每次求出某分数值时要约分到最简。这里所谓的“高精度”比较有意思的是，用质因数分解的方式保存各个值，这样可非常简便地求gcd和lcm。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

#define MAXP 1300
#define MAXT 5000
#define SIZEP 4*MAXP
#define SIZET 4*MAXT

int n,d[1000],p[MAXP]={2,3};
int nu[MAXP],de[MAXP],tnu[MAXP],tde[MAXP];
int t[MAXT];

void gcd(int a[],int b[])
{
    int i;
    for(i=0;i<MAXP;i++)
        t[i]=min(a[i],b[i]);
}

void lcm(int a[],int b[])
{
    int i;
    for(i=0;i<MAXP;i++)
        t[i]=max(a[i],b[i]);
}

void div(int a[],int b[])
{
    int i;
    for(i=0;i<MAXP;i++)
        a[i]-=b[i];
}

void pnt(int a[])
{
    int i,j,k,l;
    memset(t,0,SIZET);
    for(i=0,t[0]=1;i<MAXP;i++)
    {
        if(!a[i]) continue;
        j=1;
        while(a[i]--)
            j*=p[i];
        for(l=0;l<MAXT;l++)
            t[l]*=j;
        for(l=0;l<MAXT-1;l++)
        {
            t[l+1]+=t[l]/10;
            t[l]%=10;
        }
    }
    for(l=MAXT-1;!t[l];l--);
    for(;l>-1;l--)
        printf("%d",t[l]);
}

void calc(int a,int b[])
{
    int i;
    memset(b,0,SIZEP);
    for(i=0;a>1;i++)
    {
        while(a%p[i]==0)
        {
            b[i]++;
            a/=p[i];
        }
    }
}

int main()
{
    int i,j,k,l;
    for(i=2;i<MAXP;i++)
    {
        for(j=p[i-1]+2;1;j+=2)
        {
            for(k=0,l=sqrt(j);p[k]<=l&&j%p[k];k++);
            if(p[k]>l)
            {
                p[i]=j;
                break;
            }
        }
    }
    while(~scanf("%d",&n))
    {
        for(i=0;i<n;i++) scanf("%d",d+i);
        sort(d,d+n);
        for(i=j=1;i<n;i++)
        {
            if(d[i]!=d[i-1])
                d[j++]=d[i];
        }
        n=j;
        calc(d[1]-d[0],nu);
        calc(d[0]*d[1],de);
        gcd(nu,de);
        div(nu,t);
        div(de,t);
        for(i=2;i<n;i++)
        {
            calc(d[i]-d[0],tnu);
            calc(d[0]*d[i],tde);
            gcd(tnu,tde);
            div(tnu,t);
            div(tde,t);
            gcd(nu,tnu);
            memcpy(nu,t,SIZE);
            lcm(de,tde);
            memcpy(de,t,SIZE);
        }
        gcd(nu,de);
        div(nu,t);
        div(de,t);
        if(!de[0])
            nu[0]++;
        else
            de[0]--;
        pnt(de);
        printf(" ");
        pnt(nu);
        puts("");
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define MAXP 1300

#define MAXT 5000

#define SIZEP 4*MAXP

#define SIZET 4*MAXT

int n,d[1000],p[MAXP]={2,3};

int nu[MAXP],de[MAXP],tnu[MAXP],tde[MAXP];

int t[MAXT];

void gcd(int a[],int b[])

{

int i;

for(i=0;i<MAXP;i++)

t[i]=min(a[i],b[i]);

}

void lcm(int a[],int b[])

{

int i;

for(i=0;i<MAXP;i++)

t[i]=max(a[i],b[i]);

}

void div(int a[],int b[])

{

int i;

for(i=0;i<MAXP;i++)

a[i]-=b[i];

}

void pnt(int a[])

{

int i,j,k,l;

memset(t,0,SIZET);

for(i=0,t[0]=1;i<MAXP;i++)

{

if(!a[i]) continue;

j=1;

while(a[i]--)

j*=p[i];

for(l=0;l<MAXT;l++)

t[l]*=j;

for(l=0;l<MAXT-1;l++)

{

t[l+1]+=t[l]/10;

t[l]%=10;

}

for(l=MAXT-1;!t[l];l--);

for(;l>-1;l--)

printf("%d",t[l]);

}

void calc(int a,int b[])

{

int i;

memset(b,0,SIZEP);

for(i=0;a>1;i++)

{

while(a%p[i]==0)

{

b[i]++;

a/=p[i];

}

int main()

{

int i,j,k,l;

for(i=2;i<MAXP;i++)

{

for(j=p[i-1]+2;1;j+=2)

{

for(k=0,l=sqrt(j);p[k]<=l&&j%p[k];k++);

if(p[k]>l)

{

p[i]=j;

break;

}

while(~scanf("%d",&n))

{

for(i=0;i<n;i++) scanf("%d",d+i);

sort(d,d+n);

for(i=j=1;i<n;i++)

{

if(d[i]!=d[i-1])

d[j++]=d[i];

}

n=j;

calc(d[1]-d[0],nu);

calc(d[0]*d[1],de);

gcd(nu,de);

div(nu,t);

div(de,t);

for(i=2;i<n;i++)

{

calc(d[i]-d[0],tnu);

calc(d[0]*d[i],tde);

gcd(tnu,tde);

div(tnu,t);

div(tde,t);

gcd(nu,tnu);

memcpy(nu,t,SIZE);

lcm(de,tde);

memcpy(de,t,SIZE);

}

gcd(nu,de);

div(nu,t);

div(de,t);

if(!de[0])

nu[0]++;

else

de[0]--;

pnt(de);

printf(" ");

pnt(nu);

puts("");

}

return 0;

}