首页 > 其他分享 >洛谷 P7517 [省选联考 2021 B 卷] 数对

洛谷 P7517 [省选联考 2021 B 卷] 数对

时间:2024-10-10 20:21:32浏览次数:9  
标签:P7517 cnt int 数对 cin long mx tie 联考

题目传送门

解题思路

其实你只要知道:

n \times \sum _{i=1} ^{n} n/i= n \log n

这题你就秒了。

我们发现 a_i \leq 5 \times 10^5,于是开一个桶来统计每个数出现的数量。

我们只需要枚举每一个数的倍数,然后统计。

最后,如果一个数出现了多次,再特判一下即可。

代码

#include<bits/stdc++.h>
using namespace std;

int n;
int cnt[500001];
int mx;
long long ans;
long long temp;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	int x;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		mx=max(mx,x);
		cnt[x]++;
	}
	
	for(int i=1;i<=mx;i++)
	{
		temp=0;
		for(int j=2;j<=mx/i;j++)
		{
			temp+=cnt[i*j];
		}
		temp+=cnt[i]-1;
		temp*=cnt[i];
		ans+=temp;
	}
	cout<<ans;
	return 0;
}

标签:P7517,cnt,int,数对,cin,long,mx,tie,联考
From: https://blog.csdn.net/2403_87021226/article/details/142723224

相关文章

  • 3162. 优质数对的总数 I
    给你两个整数数组nums1和nums2,长度分别为n和m。同时给你一个正整数k。如果nums1[i]可以被nums2[j]*k整除,则称数对(i,j)为优质数对(0<=i<=n-1,0<=j<=m-1)。返回优质数对的总数。示例1:输入:nums1=[1,3,4],nums2=[1,3,4],k=1输出:5解释:5......
  • [省选联考 2024] 魔法手杖
    一年之后再看好歹是会双log做法的84分的,虽然可能被卡常首先显然有\(x\oplusy\lex+y\)。对于一个最优的方案\(S,x\)你显然如果不影响$\oplus$部分的最值的话移走的最优的。所以我们只会将会影响$\oplus$部分最值的留在\(S\)。考虑二分答案\(mid\),判断有没有\(\ge......
  • 10.8日noip联考总结
    10.8日noip联考总结T1考试的时候没有想到可以快速用组合数进行统计答案,于是在正常的匹配栈里还套了一个\(O(n)\)的统计答案。其实只需要在里面统计个数,在用乘法原理就可以了。括号匹配引导我们使用匹配栈,而需要快速统计答案又可以想到组合计数。T2这题不用输出方案的话就......
  • 10.7 noip多校联考与牛客CSP-S总结
    我在这里对我今天在牛客考试中进入洛谷做出深刻的反省,我不应该在考试的时候上与考试无关的网站(洛谷),保证没有下犯,在该做什么的时候就做什么,分清主次。10.7noip多校联考与牛客CSP-S总结noip联考T1是一道类似于概率计数DP的题,统计概率。通过题目给出的信息,可以发现使用概率,而统......
  • 华为OD机试真题---整数对最小和
    题目描述给定两个整数数组array1和array2,数组元素按升序排列。假设从array1和array2中分别取出一个元素可构成一对元素。现在需要取出K个元素对(即从两个数组中各取一个元素组成一个对,共取K个这样的对),并对取出的所有元素求和,计算和的最小值。注意:两对元素如果对应于array1和......
  • 10.2与10.3日noip多校联考总结
    10.2与10.3noip多校联考总结10.2T1考场上推了比较久,想到了对于每个二进制位进行贪心,但是往上面套了二分和判定,导致时间复杂度到了\(O(T\log^3n)\),时间过劣。在考后知道了二分和判定都可以省去。因为要求最小次数,所以不免想到了二分和贪心,用学长讲的“调整法”就可以很好......
  • [2023四校联考3]sakuya 题解(根号分治)
    题目链接。题目分析第一个操作类似哈希冲突那一道题,可以运用类似的思路开一个二维表,很容易想到两种做法:开一个二维表,表上的第\(i\)行,第\(j\)列表示序列下标在模\(i\)意义下等于\(j\)的加法标记。对于修改操作,直接暴力修改对应的那一行的值即可,查询时用线段树查询那个......
  • 联考题解
    联考题解龙(dragon)难点:(1)删边后如何寻找新的最短路。(2)A,B两方的决策互相影响十分复杂。(3)如何统计每个起点的ans。解题:(3)解决这类多起点一终点的问题,可以想到dp。(1)解决这类最短路转移的问题,可以考虑最短路树。(2)解决这类博弈问题,可以设计两个dp数组,分别维护影响前后的ans,在转移......
  • [2023四校联考3]sakuya
    [2023四校联考3]sakuya题意给出一棵\(n\)个点的树,有\(m\)个特殊点\(a\),求将\(a\)随机打乱后\[\sum_{i=2}^md(a_{i-1},a_i)\bmod998244353\]的期望。有\(q\)次修改,每次将一个点连接的所有边权值增加。思路发现期望可以变为求和。记\(S\)为所有情况的和,\(\frac......
  • [2023四校联考3]meirin
    [2023四校联考3]meirin题意给出两个序列\(a,b\),\(b\)需要支持区间加。每次修改完后求:\[\sum_{l=1}^n\sum_{r=l}^n(\sum_{i=l}^{r}a_i)\times(\sum_{i=l}^{r}b_i)\bmod10^9+7\]思路发现\(a\)没有修改,考虑把\(a\)作为\(b\)的系数单独计算。把原式变为:\[\sum_{i=1......