Problem #2536 - ECNU Online Judge

10165101104

7 年，6 月前

楼上数据有误吧：
input：
1
2
3
4
5
6
7
8
9
10
11
12
13

output：
2/1
7/2
31/6
203/30
1007/120
15611/1560
42319/3640
819523/61880
10116217/680680
998361233/60580520
19734909839/1090449360
5009333401207/254074700880
157192635368603/7368166325520

回复 0 0

Commando

3 年前

#include <bits/stdc++.h>

using namespace std;

using ull = unsigned long long;
using pairuu = pair<ull, ull>;

static vector<ull> fib(20);
static unordered_map<int, pairuu> memo;

pairuu sum(int n) {
    if (n == 1) return make_pair(2, 1);
    if (memo[n].first != 0) return memo[n];

    auto [x0, y0] = make_pair(fib[n + 2], fib[n + 1]);
    auto [x1, y1] = sum(n - 1);

    ull c = lcm(y0, y1);

    return memo[n] = make_pair(x0 * (c / y0) + x1 * (c / y1), c);
}

int main() {
    fib[1] = fib[2] = 1;
    for (int i = 3; i < 20; ++i) fib[i] = fib[i - 1] + fib[i - 2];

    int t, n;
    cin >> t;
    while (t--) {
        cin >> n;
        auto [x, y] = sum(n);
        auto c = gcd(x, y);
        x /= c, y /= c;

        cout << x << '/' << y << endl;
    }
}

回复 0 0

10165101223

8 年前

y wa?
代码不大好看…

include

long long divisor(long long a,long long b)
{
long long c;
while(a%b!=0)
{
c=a%b;
a=b,b=c;
}
return c;
}
int main()
{
int f[15]={1,1,2,3,5,8,13,21,34,55,89,144,233,377,610};
int t;
long long a,b;
scanf(“%d”,&t);
int i=0;
int first=1;
for(i=0;i<t;i++)
{
if(first==0)
{
printf(“\n”);
}
int max,j;
scanf(“%d”,&max);
a=f[2],b=f[1];
for(j=1;j<max;j++)
{
a=af[j+1]+bf[j+2],b*=f[j+1];
a/=divisor(a,b),b/=divisor(a,b);
}
printf(“%I64d/%I64d”,a,b);
first=0;
}
}
test input:
13
1
2
3
4
5
6
7
8
9
10
11
12
13
test output
2/1
7/2
31/6
203/30
1007/240
18131/3120
162277/65520
4560509/2227680
89818303/122522400
25637054567/10904493600
43281131017/1570247078400
602067652083761/365867569267200
34627594006813069/137932073613734400

回复 0 0

Saitama

6 年，7 月前

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long LL;

LL gcd(LL a, LL b)
{
    if(a < b)
        return gcd(b, a);
    else
        return a % b == 0 ? b : gcd(a % b, b);
}

typedef struct zz
{
    LL fenzi;
    LL fenmu;
}zz;

int main()
{
    LL fi[17];
    fi[0] = 1;
    fi[1] = 1;
    for(int i = 2; i < 17; i++)
        fi[i] = fi[i - 1] + fi[i - 2];
    vector <zz> a(17);
    vector <zz> sum(17);
    for(int i = 0; i < 17; i++)
    {
        a[i].fenzi = fi[i + 2];
        a[i].fenmu = fi[i + 1];
    }
    sum[0].fenmu = a[0].fenmu;
    sum[0].fenzi = a[0].fenzi;
    for(int i = 1; i < 17; i++)
    {
        sum[i].fenmu = sum[i - 1].fenmu * a[i].fenmu;
        sum[i].fenzi = sum[i - 1].fenzi * a[i].fenmu + sum[i - 1].fenmu * a[i].fenzi;
    }
    int T;
    cin >> T;
    for(int i = 0; i < T; i++)
    {
        int n;
        cin >> n;
        cout << sum[n - 1].fenzi / gcd(sum[n - 1].fenmu, sum[n - 1].fenzi) << '/' << sum[n - 1].fenmu / gcd(sum[n - 1].fenmu, sum[n - 1].fenzi) << endl;
    }
    return 0;
}

重做基本题

回复 0 0

e_mmmmmm

6 年，8 月前

int a[16]={0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610};

ll gcd(ll s,ll d){
ll c=1;
while(s%d!=0){
c=s%d;
s=d;
d=c;
}
return c;
}

int main(int argc, char const argv[]){
int cas;
cin>>cas;
while(cas–){
int n;
cin>>n;
int r=n+1;
ll d=1;
for(int i=2;i<=r;i++)
d=a[i];
ll s=0;
for(int i=3;i<=r+1;i++)
s+=(a[i]*(d/a[i-1]));
ll c=gcd(s,d);
cout<<s/c<<”/”<<d/c<<endl;
}
return 0;
}

回复 0 0

2536. 求和

include

服务

开源

关于我们