牛客多校赛题解（七）

1.Xay loves count

题目链接：H-xay loves count_2021牛客暑期多校训练营7 (nowcoder.com)

题目大意

有一个长度为n的数组a，需要求三个下标：i, j, k满足ai * aj = ak

解题思路

本题由于对 i , j , k 大小关系无要求，因此需要考虑排列组合的方式。在数组中，找某个数的约数是否存在比判断两数之积是否存在更方便一些，因此可遍历判断某数的约数是否在数组中成对出现。

本题对时间复杂度较为严格，需要控制在 nlogn ，因此对于数组中的重复元素需要进行跳步，即记录个数进行相乘。而对于 i，j，k 的特殊性，当该对约数并不相等时，还需要乘 2 对排列组合进行考虑。

/*
 * @Author: Shadowlove
 * @Date: 2021-07-27 21:55:12
 * @LastEditors: Shadowlove
 * @LastEditTime: 2021-08-07 13:03:20
 * @Description: file content
 */
#include <bits/stdc++.h>
using namespace std;
int n;
int arr[1200000];
int boo[1200000];
int main()
{
     
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        boo[arr[i]]++;
    }
    sort(arr, arr + n);
    long long ans = 0;
    for (int i = 0; i < n; i++)
    {
        int cnt = arr[i];
        //cout<<"nowcnt=="<<cnt<<endl;
        for (int j = 1; j <= sqrt(cnt); j++)
        {
            if (cnt % j== 0 && boo[j] && boo[cnt/ j])
            {
                if (j == cnt / j)
                    ans += boo[j]* boo[cnt/j];
                else
                    ans += boo[j] * boo[cnt/j] * 2;
            }
        }
        //cout<<ans<<endl;
    }
    cout << ans << endl;
    return 0;
}

参考链接：xay loves count（2021牛客多校第七场H）_国家一级划水运动员的博客-CSDN博客

2.xay loves or

题目链接：I-xay loves or_2021牛客暑期多校训练营7 (nowcoder.com)

题目大意

给定x和s，求解有多少y满足x|y = s

解题思路

1. x = 1，s = 0，此时 y 无解，直接输出 0 即可；
2. x = 1，s = 1，此时 y 可为 0 或 1 ，即 y * = 2；
3. x = 0，s = 0，此时 y 只能为 0；
4. x = 0，s = 1，此时 y 只能为 1；

ACCode

/*
 * @Author: Shadowlove
 * @Date: 2021-07-27 21:55:12
 * @LastEditors: Shadowlove
 * @LastEditTime: 2021-08-07 13:03:20
 * @Description: file content
 */
#include <bits/stdc++.h>
using namespace std;
int main()
{
 
    long long ans = 1;
    int cnt = 0;
    int x, y, s;
    cin >> x >> s;
    for (int i = 0; i <= 30; i++)
    {
        int bitx = (x >> i) & 1;
        int bits = (s >> i) & 1;
        if (bitx == 1 && bits == 1)
        {
            ans = ans * 2;
            cnt++;
        }
        else if(bitx==0&&bits==0)
            cnt++;
        else if (bitx == 1 && bits == 0)
        {
            ans = 0;
            break;
        }
    }
    if((x|0)==s)
        ans--;
    cout << ans << endl;
    return 0;
}