The 2021 ICPC Asia Shanghai Regional Programming Contest 2021ICPC上海站VP

PS：实际打了2两个小时左右，被叫走去干活了。所以就直接补题了

ABCDEFGHIJKLM––补ACAC–ACACAC补补–补 C.Strange Matrices 状压DP

待补

D. Strange Fractions 数学/暴力 题目分析

对于给定的 p , q p, q p,q，找到 a , b a, b a,b满足 p q = a b + b a \frac{p}{q} = \frac{a}{b} + \frac{b}{a} qp​=ba​+ab​。找不到输出 0   0 0\ 0 0 0

令 x = a b x = \frac{a}{b} x=ba​，则 p q = x + 1 x \frac{p}{q} = x + \frac{1}{x} qp​=x+x1​，故可得： q x 2 − p x + q = 0 qx^2 - px + q = 0 qx2−px+q=0，方程解为有理数时 p 2 − 4 q 2 \sqrt{p^2 - 4q^2} p2−4q2 ​为有理数，则 p 2 − 4 q 2 p^2 - 4q^2 p2−4q2为完全平方数。那么对于是否有解只需判断 ( p 2 − 4 q 2 ) 2 = = p 2 − 4 q 2 (\sqrt{p^2 -4q^2})^2 == p^2 - 4q^2 (p2−4q2 ​)2==p2−4q2即可。

Code

#include 
#define int long long
#define end '\n'
using namespace std;


inline void solve(){
    int p, q; cin >> p >> q;
    int res = pow(p * p - 4 * q * q, 0.5);
    if(res * res == p * p - 4 * q * q){
        int det = sqrt(p * p - 4 * q * q), a = 0, b = 2 * q;
        if(det > p) a = p + det;
        else a = p - det;
        cout  w;
        add_edge(i, u, v ,w);
    }
    n = kruskal();
    dfs0(n, 0);
    val[0] = 1e18;
    while(q--){
        int u, s; cin >> u >> s;
        int ans = pnt[u] + s;
        while(u != n){
            int t = u;
            for(int i = 19; i >= 0; i--)
                if(val[fa[u][i]]  v[i] >> t[i];
    
    for (int i = 0; i > b;
    a = '@' + a, b = '@' + b;
    for(int i = 1; i  (n - pos));
                if(s[pos] > 0) tg = min(tg, pos + 1);
            }
        }
        A[n - pos] = 1;
    }
    for(int i = 1; i = tg) cout