idol!!

题目大意

给定一个数n，求1~n所有双阶乘的乘积末尾0的个数。

正整数的双阶乘表示不超过这个正整数且与它有相同奇偶性的所有正整数乘积。

解题思路

可以发现，只需找2的因子数量和5的因子数量取min即可，但显然2的因子数量远小于5，所以我们只需要找5的因子数量就是答案。

考虑每个数对答案的贡献，这里我的做法是奇偶讨论。

先看奇数部分，

5，7，9，11，…这些数x对答案的贡献都为

25，50，75，…，这些数x对答案的贡献都为

依次类推。

那么我们可以这么算，5, 7, 9, 11, …, n-n%2，这些数先对答案的贡献加，

然后25, 50 ,75,…，这些数再对答案的贡献加。

这样我们就可以写成一个循环，循环中套一个等差数列的求和来完成奇数部分计算。

接下来是偶数部分，

同理，

10, 20, 30, …对答案贡献加上.

50, 100,150,…对答案贡献加上,

以此类推。

同样，一个循环加等差数列求和即可。

由于会爆long long，所以可以用int128解决。

时间复杂度：

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>

using namespace std;

typedef long long i64;
typedef __int128_t i128;

inline __int128 read()
{
    __int128 X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}

inline void print(__int128 x)
{    
    if(x<0){putchar('-');x=-x;}
    if(x>9) print(x/10);
    putchar(x%10+'0');
}



bool multicase=0;

void solve(){
    i128 n = read();

    i128 ans = 0;
    
    for (i128 i = 5; i <= n; i *= 5){
        i128 a1 = (n - i + 2) / 2, tn = (n - i) / (2 * i) + 1, d = (-i);
        ans += a1 * (tn) + (tn * (tn - 1) / 2) * (d); 
    }

    for (i128 i = 10; i <= n; i *= 5){
        i128 a1 = (n - i + 2) / 2, tn = n / i, d = (-i / 2);
        ans += a1 * (tn) + (tn * (tn - 1) / 2) * (d); 
    }

    print(ans);
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int CASE=1;
    if(multicase) cin>>CASE;
    while(CASE--){
        solve();
    }

    return 0;
}

Sequence

题目大意

给定一组数列，每次问你之间能否构造出恰好k个连续的组，使得每组和为偶数。

解题思路

可以发现，求之间能否构造出恰好k个连续偶数组，我们可以从到，每次加这一位上的数，形成偶数就累加，看这部分偶数的个数能否大于等于k，因为如果大于k，我们可以合并若干组使得形成k组。

首先，预处理前缀和，用来判断l和r之间是否和为偶数，以及1~l-1奇数还是偶数。

然后从1到n遍历，sum分别从0或1开始，每次加上当前值，若形成偶数则sum=0，这一位上计数，然后分别求前缀和。

这时若查询l到r，那么看1~l-1是偶数还是奇数，如果是偶数，那么前面一定能形成完整的偶数区间，到第l位时sum为0，所以我们选择从sum从0开始的进行计算，否则选择从1开始的。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
//#define x first
//#define y second

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;

const int mod=1e9+7;
const double eps=1e-8;
/*=================================*/
bool multi=1;
const int N=1e5+10;
int a[N];
int sum1[N],sum2[N];
int suma[N];

void solve(){
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        sum1[i]=sum2[i]=0;
    }
    for(int i=1;i<=n;i++){
        cin>>a[i];
        suma[i]=suma[i-1]+a[i];
    }
    int sum=0;
    for(int i=1;i<=n;i++){
        sum+=a[i];
        if(sum%2==0){
            sum1[i]++;
            sum=0;
        }
    }
    sum=1;
    for(int i=1;i<=n;i++){
        sum+=a[i];
        if(sum%2==0){
            sum2[i]++;
            sum=0;
        }
    }
    for(int i=1;i<=n;i++){
        sum1[i]+=sum1[i-1];
        sum2[i]+=sum2[i-1];
    }
    while(q--){
        int l,r,k;
        cin>>l>>r>>k;
        if((suma[r]-suma[l-1])%2==0){
            if(suma[l-1]%2==1){
                if(sum2[r]-sum2[l-1]>=k){
                    cout<<"YES"<<endl;
                }else{
                    cout<<"NO"<<endl;
                }
            }else{
                if(sum1[r]-sum1[l-1]>=k){
                    cout<<"YES"<<endl;
                }else{
                    cout<<"NO"<<endl;
                }
            }
        }else{
            cout<<"NO"<<endl;
        }
    }

}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

Gcd

题目大意

给定一个集合S={x,y}，每次可以选择集合内两个不同元素a,b，将a-b或gcd(|a|,|b|)的结果加入到集合中，问经过任意次操作后能否使集合中存在z。

解题思路

显然，z为0时，若a，b都不为0，则一定不会构造出0，否则可以。

z不为0时，当z小于等于max(a,b)且gcd(a,b)|z，则可以构造，否则不能构造。因为a-b一定是gcd(a,b)的倍数，因此max(a,b)每次可以减若干个gcd(a,b)得到min(a,b)，所以不需要找a-b,直接看max(a,b)能否减去若干个gcd(a,b)后得到z，而max(a,b)又一定是gcd(a,b)的倍数（根据最大公约数性质），所以直接判断z能否整除gcd(a,b)即可。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>

using namespace std;

bool multicase=1;

void solve(){
    int x,y,z;
    cin>>x>>y>>z;
    int d=__gcd(x,y);

    if(z==0){
        if(x==0||y==0){
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
        return;
    }

    if(z<=max(x,y)&&z%d==0){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int CASE=1;
    if(multicase) cin>>CASE;
    while(CASE--){
        solve();
    }

    return 0;
}