9.28 普及模拟赛总结

__S08577__ · 2024-09-28 10:53:27 · 个人记录

T1

这道题要求从 1 到 n 里约数是偶数个数的数的个数。不难发现，只有完全平方数的约数个数是奇数个，其余的所有数约数个数都是偶数个。

注意，sqrt 的返回值是 double，当使用 sqrt(i)*sqrt(i) 时应当写成 (int) sqrt(i)*(int) sqrt(i) 不然会导致大部分的数都符合条件。

T2

求 x \times y \mod z 的值，x,y \le 10^{18}。

要是题目为x^ y \mod z 的值，x,y \le 10^{18} 那么不难想到这道题用快速幂可做，而 x^y 为 y 个 x 相乘，x \times y 为 y 个 x 相加，只需要把快速幂中的乘改成加即可。

inline int ksj(int a,int b,int Mod){
    long long res=0;
    while(b>0){
        if(b&1)
            res=(res+a)%Mod;
        a=(a+a)%Mod;
        b>>=1;
    }
    return res%Mod;
}

T4

只会Kruscal不会Prim

int 函数一定要有返回值！

int 函数一定要有返回值！

int 函数一定要有返回值！

不然会出现全部RE的情况！