其实是每日一题看到复杂版本的题解已经写了一大堆了，简单版本这里没人写题解所以来抢占先机写个题解，其实做法跟困难版本的一模一样，代码交上去也能过困难版本的
一个数的末尾有k个0实际上就代表了它的因子里起码是有k个2以及k个5的，不难想到处理x的末尾有多少个0可以使用两个前缀和数组，分别累加到a[i]为止每项元素里因子里2的个数和5的个数的累加
然后是本题的一个关键转化，恰有k个的数量=大于等于k个的数量-大于等于k+1个的数量，然后大于等于k/k+1个是可以用二分去进行处理的（当然，双指针处理也是可以的，但我双指针写的很差导致这种题能用二分就用的二分来着）
满足从a[l]一直到a[r]乘积末尾有大于等于x个0的等价条件是pre2[r] - pre2[l - 1] >= x && pre5[r] - pre5[l - 1] >= x,以此作为二分的条件判断
时间复杂度O(nlogn)
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << '\n';
// #define int long long
#define ctz __builtin_ctzll // 返回二进制表示中末尾连续0的个数
#define clz __builtin_clzll // 返回二进驻表示中先导0的个数
#define count1 __builtin_popcountll // 返回二进制表示中1的个数
// 上面仨不是ll的时候记得调整
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int hash_base = 881;
const int N = 1e6 + 10000;
const double EPS = 1e-8;
const ll MOD = 676767677;
// const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
ll dirr[8][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
void LiangBaiKai()
{
}
void Aiden()
{
ll m, n, k, sum = 0, ans = 0, num = 0, mi = INF, ma = -INF, cnt = 0, x, y, z, len, t, l, r, cur;
string s1, s2;
cin >> n >> k;
vector<ll> a(n + 1), cnt2(n + 1), cnt5(n + 1), pre2(n + 1), pre5(n + 1);
for (ll i = 1; i <= n;i++)
{
cin >> a[i];
x = a[i];
while (x % 2 == 0) // 判断因子里有多少个2
{
cnt2[i]++;
x /= 2;
}
x = a[i];
while (x % 5 == 0) // 判断因子里有多少个5
{
cnt5[i]++;
x /= 5;
}
pre2[i] = pre2[i - 1] + cnt2[i]; // 分别累加前缀和
pre5[i] = pre5[i - 1] + cnt5[i];
}
auto count = [&](ll x,ll i) -> ll // 写一个二分来统计末尾大于等于x个0的数量
{
ll res = 0;
l = i - 1;
r = n + 1;
while (l + 1 != r)
{
ll mid = (l + r) >> 1;
if (pre2[mid] - pre2[i - 1] >= x && pre5[mid] - pre5[i - 1] >= x) // 二分判别条件
r = mid;
else
l = mid;
}
res += (n - l);
return res;
};
for (ll i = 1; i <= n;i++)
ans += count(k, i) - count(k + 1,i); // 恰有k个的数量=大于等于k个的数量-大于等于k+1个的数量
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
LiangBaiKai();
int _ = 1;
cin >> _;
while (_--)
Aiden();
return 0;
}
/*
@@@@@@
@@@@@@@@@@
@@@@@@@@@@@@@
@@@@@@@@@@@@@@@
@@@@@@@@@@@
@@@@
@
@@@@@@@@@@ @@ @@@@@@@@@@@@
@@@@@ @ @@@@@
@@@ @ @@@
@@@ @@ @@@
@@ @@@
@@ @@
@@ @@
@@ @@
@ @@
@ @@@@@@@@ @@
@ @@@ @@@@@@@@@ @
@@ @@@@@@@ @@@@@@@@ @@@@@@ @
@ @@@@@@@@@@@@@@@@@@@@@@@@@@ @@
@ @@@@@@@@@@@ @@@@@@@@@@@ @
@@@@@@@@@@@@@ @@@@@@@@@@@@@@ @ @@@@@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ @@@@@@ @@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@ @@@ @@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@
@@@@@@ @@@@@@@@@@ @@@@@@@@@@@@@@ @@
@@@@@ @@@@@@@ @@@@@@ @@ @@@@@@@@@@@ @@@
@@@@@ @@@@@@@@ @@@@ @@@@@@@ @@@@@@@@@@@ @@
@@@@@@ @@@@@@@ @@@@@ @@@@@@@ @@@@@@@@@@@@ @@@@@@@
@@@@@@@ @ @@@@@@ @@@@@@@ @@@@@@@@@@@@@@@@ @@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@ @ @@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ @ @ @@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ @@@@@ @ @@@@ @ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ @@ @@ @@@ @@@@@ @@@@@@@@@@
@@@@@@@ @@@@@@@@@@@@@@ @@@@@@ @@@@@ @ @@@@@@@@
@@@@@@ @@@@@@@@@@@ @ @@@@@@@@
@@@@ @@@@@@@@ @@ @@@@@@@
@@ @@ @@@@@
@@@ @@
@@@ @@@
@@@@@@@@@@@@ @@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
*/
京公网安备 11010502036488号