蜃楼观光

NC229814. 蜃楼观光

描述

传说中，三目是在蜃气楼作为猫侍应的妖怪，他总是在工作与摸鱼中切换，今天的三目准备在蜃气楼的商店街里摸鱼。

商店街上从左到右有 $n$ 个摊位，标号分别为 $1, 2, \ldots, n$ ，第 $i$ 个摊位有一个观光值 $w_i$ ，表示该摊位吸引人的程度。此外， $w_1, w_2, \ldots, w_n$ 恰好是一个 $1, 2, \ldots, n$ 的排列。三目的时间有限，因此他只能观光最多三个摊位。为此，三目定义完美观光路线 $(i, j, k)$ 为满足如下条件的三元组：

$1 \leq i < j < k \leq n$
$\gcd(w_i, w_j) \leq \gcd(w_j, w_k)$

其中， $\gcd(a, b)$ 表示 $a$ 与 $b$ 的最大公约数。

三目想知道一共有多少种完美观光路线。他正在匆忙赶去商店街的路上，因此请你帮他计算出这个结果。

输入描述

第一行为一个整数  ()，表示商店街上摊位的个数。

第二行为  个用空格分隔的整数 ，表示每个摊位的观光值。

保证  是一个  的排列。

输出描述

输出一行一个整数，表示一共有多少种完美观光路线。

示例1

输入:

5
1 2 3 4 5

输出:

说明:

一共有 $9$ 种完美观光路线： $(1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5), (3, 4, 5)$ 。

示例2

输入:

7
3 4 1 7 5 2 6

输出:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 259ms, 内存消耗: 20040K, 提交时间: 2022-01-23 13:37:28

#include<iostream>
#include<vector>
#define ll long long
using namespace std;
const int N = 1e5+5;
vector<ll> d[N];
ll w[N],l[N],r[N],f[N],g[N];
int n;
ll ans;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>w[i];
	for(int i=n;i>=1;i--)
		for(int j=i;j<=n;j+=i)
			d[j].push_back(i);
	for(int i=1;i<=n;i++) r[i]=n/i;
	for(int x:d[w[1]]) r[x]--;
	for(int j=2;j<n;j++)
	{
		for(int x:d[w[j-1]]) l[x]++;
		for(int x:d[w[j]]) r[x]--;
		for(int x:d[w[j]])
		{
			f[x]=l[x],g[x]=r[x];
			for(int y:d[w[j]])
				if(y%x==0&&y>x)
					f[x]-=f[y],g[x]-=g[y];
		}
		for(int x:d[w[j]])
			for(int y:d[w[j]])
				if(x<=y)
					ans+=f[x]*g[y];
	}
	cout<<ans<<endl;
	return 0;
}

上一题

下一题

详情