游游的选数乘积

[编程题]游游的选数乘积

热度指数：184 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

游游拿到了一个数组，她准备在其中选择两个数，使得乘积的末尾至少有 $x$ 个0。游游想知道，至少有多少种不同的取数方法？

输入描述:

第一行输入两个正整数和，代表数组的大小以及乘积末尾的数量。
第二行输入个正整数，代表游游拿到的数组。

输出描述:

输出一个整数，代表游游选择的方案数。

示例1

输入

5 2
3 5 50 2 80

输出

说明

5*80=400，末尾有2个0。
50*2=100，末尾有2个0。
50*80=4000，末尾有3个0。
有以上3种方案满足乘积至少有2个0。

算法知识视频讲解

喜欢白菜

#include <iostream>
#include <string>
using namespace std;
#include<bits/stdc++.h>
//pow(2,30)>1e9
//pow(5,20)>1e9
int nums[31][21];
//求一个数末尾有多少个0，即求2和5相等的个数

int main() {
  int n, x;
  long long res = 0;
  cin >> n >> x;
  for (int i = 0; i < n; ++i)
  {
    int a;
    scanf("%d", &a);
    int x = 0, y = 0;
    while (a % 2 == 0)
    {
      ++x;
      a /= 2;
    }
    while (a % 5 == 0)
    {
      ++y;
      a /= 5;
    }
    ++nums[x][y];//a由x个2，y个5组成
  }
  for (int i = 0; i <= 30; ++i)
  {
    for (int j = 0; j <= 20; ++j)
    {
      //统计末尾0个数一样的
      if (nums[i][j])
      {
        int k1 = min(i, j);

        if (2 * k1 >= x)
        {
            
          res += nums[i][j] * (nums[i][j] - 1);
        }
      }
      else
        continue;
      for (int i2 = 0; i2 <= 30; ++i2)
      {
        for (int j2 = 0; j2 <= 20; ++j2)
        {
          if (i2 == i && j2 == j||nums[i2][j2]==0)continue;
          int k2 = min(i2 + i, j2 + j);
          if (k2 >= x)
          {
            res += nums[i][j] * nums[i2][j2];
          }
        }
      }
    }
  }
////算两遍(a,b) (b,a).所以最后/2
  printf("%lld", res / 2);
  return 0;

}
// 64 位输出请用 printf("%lld")

发表于 2023-06-26 22:37:56 回复(0)

Tom_P

诈骗题，选两个数最多只能有18个0，实际上数据范围很小，可以枚举。

发表于 2024-03-15 13:39:09 回复(0)

yq19

n, x = map(int, input().split())
nums = list(map(int, input().split()))
 
n5n2 = [ [0]*30 for _ in range(13)] # [n5][n2]
 
def cnt_of_5_2(x):
    cnt_of_5 = 0
    cnt_of_2 = 0
    while x % 5 == 0:
        x //= 5
        cnt_of_5 += 1
    while x % 2 == 0:
        x //= 2
        cnt_of_2 += 1
    return cnt_of_5, cnt_of_2
 
for num in nums:
    a, b = cnt_of_5_2(num)
    n5n2[a][b] += 1
 
cnt = 0
for i1 in range(0, 13):
    for j1 in range(0, 30):
        for i2 in range(i1, 13):
            for j2 in range(0, 30):
                if i1 == i2 and j2 < j1:
                    continue
                if i1 + i2 >= x and j1 + j2 >= x and n5n2[i1][j1] > 0 and n5n2[i2][j2] > 0:
                    if i1 == i2 and j1 == j2:
                        cnt += n5n2[i1][j1] * (n5n2[i1][j1] - 1) // 2
                    else:
                        cnt += n5n2[i1][j1] * n5n2[i2][j2]
 
#print(n5n2)
print(cnt)

发表于 2023-10-08 19:47:42 回复(0)

openallzzz

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 100010;

int n, m;
int a[N];

int cnt[40][30];

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> a[i];

    for(int i = 1; i <= n; i ++) {
        int c2 = 0, c5 = 0, t = a[i];
        while(t % 2 == 0) c2 ++ , t /= 2;
        while(t % 5 == 0) c5 ++ , t /= 5;
        cnt[c2][c5] ++ ;
    }

    ll ans = 0;
    for(int i = 1; i <= n; i ++) {
        int c2 = 0, c5 = 0, t = a[i];
        while(t % 2 == 0) c2 ++ , t /= 2;
        while(t % 5 == 0) c5 ++ , t /= 5;

        cnt[c2][c5] -- ;

        for(int j = 0; j < 40; j ++) {
            for(int k = 0; k < 30; k ++) {
                if(cnt[j][k] && min(j + c2, k + c5) >= m) ans += cnt[j][k];
            }
        }
    }

    cout << ans << "\n";
    return 0;
}

发表于 2023-08-13 20:08:47 回复(0)