玄关!!!
查看原帖
玄关!!!
1275819
nzlys04楼主2025/1/16 14:09
WA on test#10
#include<bits/stdc++.h>
using namespace std;

struct BigInteger 
{
    typedef unsigned long long LL;
    static const int BASE = 100000000;
    static const int WIDTH = 8;
    vector<int> s;
    BigInteger& clean(){while(!s.back()&&s.size()>1)s.pop_back(); return *this;}
    BigInteger(LL num = 0) {*this = num;}
    BigInteger(string s) {*this = s;}
    bool operator <= (const BigInteger& b) const
    {
        if (s.size() < b.s.size()) return true;
        if (s.size() > b.s.size()) return false;
        for (int i = s.size() - 1; i >= 0; --i) {
            if (s[i] < b.s[i]) return true;
            if (s[i] > b.s[i]) return false;
        }
        return true;
    }
    bool operator > (const BigInteger& b) const
    {
        return!(*this <= b);
    }
    bool operator < (const BigInteger& b) const
    {
        if (s.size() < b.s.size()) return true;
        if (s.size() > b.s.size()) return false;
        for (int i = s.size() - 1; i >= 0; --i) {
            if (s[i] < b.s[i]) return true;
            if (s[i] > b.s[i]) return false;
        }
        return false;
    }
    BigInteger& operator = (long long num) 
    {
        s.clear();
        do {
            s.push_back(num % BASE);
            num /= BASE;
        } while (num > 0);
        return *this;
    }
    BigInteger& operator = (const string& str) 
    {
        s.clear();
        int x, len = (str.length() - 1) / WIDTH + 1;
        for (int i = 0; i < len; i++) 
        {
            int end = str.length() - i*WIDTH;
            int start = max(0, end - WIDTH);
            sscanf(str.substr(start,end-start).c_str(), "%d", &x);
            s.push_back(x);
        }
        return (*this).clean();
    }
    BigInteger operator + (const BigInteger& b) const 
    {
        BigInteger c; c.s.clear();
        for (int i = 0, g = 0; ; i++) 
        {
            if (g == 0 && i >= s.size() && i >= b.s.size()) break;
            int x = g;
            if (i < s.size()) x += s[i];
            if (i < b.s.size()) x += b.s[i];
            c.s.push_back(x % BASE);
            g = x / BASE;
        }
        return c;
    }
    BigInteger operator - (const BigInteger& b) const 
    {
        assert(b <= *this);
        BigInteger c; c.s.clear();
        for (int i = 0, g = 0; ; i++) 
        {
            if (g == 0 && i >= s.size() && i >= b.s.size()) break;
            int x = s[i] + g;
            if (i < b.s.size()) x -= b.s[i];
            if (x < 0) {g = -1; x += BASE;} else g = 0;
            c.s.push_back(x);
        }
        return c.clean();
    }
    BigInteger operator * (const BigInteger& b) const {
        int i, j; LL g;
        vector<LL> v(s.size()+b.s.size(), 0);
        BigInteger c; c.s.clear();
        for(i=0;i<s.size();i++) for(j=0;j<b.s.size();j++) v[i+j]+=LL(s[i])*b.s[j];
        for (i = 0, g = 0; ; i++) {
            if (g ==0 && i >= v.size()) break;
            LL x = v[i] + g;
            c.s.push_back(x % BASE);
            g = x / BASE;
        }
        return c.clean();
    }
    BigInteger operator / (const BigInteger& b) const 
    {
        assert(b > 0);
        BigInteger c = *this;
        BigInteger m;
        for (int i = s.size()-1; i >= 0; i--) 
        {
            m = m*BASE + s[i];
            c.s[i] = bsearch(b, m).s[0];
            m = m-b*BigInteger(c.s[i]);
        }
        return c.clean();
    }
    BigInteger operator % (const BigInteger& b) const 
    {
        BigInteger c = *this;
        BigInteger m;
        for (int i = s.size()-1; i >= 0; i--) 
        {
            m = m*BASE + s[i];
            c.s[i] = bsearch(b, m).s[0];
            m = m-b*BigInteger(c.s[i]);
        }
        return m;
    }
    BigInteger bsearch(const BigInteger& b, const BigInteger& m) const
    {
        int L = 0, R = BASE-1, x;
        while (L <= R) 
        {
            x = (L+R)>>1;
            if (b*BigInteger(x)<=m) {if (b*BigInteger(x+1)>m) return BigInteger(x); else L = x + 1;}
            else R = x - 1;
        }
        return BigInteger(-1);
    }
};


ostream& operator << (ostream &out,const BigInteger& x)
{
    out << x.s.back();
    for (int i = x.s.size()-2; i >= 0; --i) 
    {
        char buf[20];
        sprintf(buf, "%08d", x.s[i]);
        for (int j = 0; j < strlen(buf); j++) out << buf[j];
    }
    return out;
}


istream& operator >> (istream &in, BigInteger &x) 
{
    string s;
    if (!(in >> s)) return in;
    x = s;
    return in;
}


struct node{
	BigInteger a,b,c;
}p[1005];
int cmp(node a,node b)
{
	return a.c<b.c;
}
int main()
{
    int n,a1,b1;
    cin>>n>>a1>>b1;
    for(int i=1;i<=n;i++)
    {
    	cin>>p[i].a>>p[i].b;
    	p[i].c=p[i].a*p[i].b;
	}
	sort(p+1,p+n+1,cmp);
	BigInteger ans=a1;
	for(int i=1;i<n;i++)
	{
		ans=ans*p[i].a;
//		cout<<ans<<" ";
	}
	BigInteger sum=(ans-ans%p[n].b)/p[n].b;
	cout<<sum;
    return 0;
}
2025/1/16 14:09
加载中...