倍增
这是一道简单数论题
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], n;
int div(int x)
{
if(x % 2 == 0)
while(x % 2 == 0) x /= 2;
if(x % 3 == 0)
while(x % 3 == 0) x /= 3;
return x;
}
int main()
{
cin >> n;
for(int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
for(int i = 1; i <= n; ++ i) a[i] = div(a[i]);
for(int i = 1; i <= n; ++ i)
{
if(a[1] != a[i])
{
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
return 0;
}
三元组
这道题目我们可以直接用stlmap套vector+stl的二分暴力来做也可以选择用前后缀分解,前后缀分解是我第一次见这种思想,会用一篇博客单独整理运用这种思想的题目
stl直接做
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int a[N];
LL ans;
int main()
{
int n, k;
cin >> n >> k;
map<LL, vector<int>>mp;
for(int i = 1; i <= n; ++ i)
{
scanf("%d", &a[i]);
mp[a[i]].push_back(i);
}
for(int i = 2; i < n; ++ i)
{
int ay = a[i];
if(a[i] % k == 0)
{
LL ax = ay / k, az = 1LL * ay * k;
if(mp.find(ax) != mp.end() && mp.find(az) != mp.end())
{
auto& v1 = mp[ax];
auto& v2 = mp[az];
int m = v2.size();
int k1 = lower_bound(v1.begin(), v1.end(), i) - v1.begin();
if(k1 >= 0)
{
-- k1;
int k2 = upper_bound(v2.begin(), v2.end(), i) - v2.begin();
ans += 1LL * (k1 + 1) * (m - k2);
}
}
}
}
cout << ans << endl;
return 0;
}
前后缀分解去做
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL a[N];
map<LL, LL>l, r;
LL ans;
int main()
{
LL n, k;
scanf("%lld%lld", &n, &k);
for(int i = 1; i <= n; ++ i)
{
scanf("%lld", &a[i]);
r[a[i]] ++;
}
for(int i = 1; i <= n; ++ i)
{
r[a[i]] --;
if(a[i] % k == 0)
{
if(l.find(a[i] / k) != l.end() && r.find(a[i] * k) != r.end())
ans += 1LL * l[a[i] / k] * r[a[i] * k];
}
l[a[i]] ++;
}
cout << ans << endl;
}
标签:周赛,typedef,const,int,LL,long,ans,102,Acwing
From: https://www.cnblogs.com/cxy8/p/17381480.html