[Acwing] 1291. 轻拍牛头 约数个数

前言

传送门:

思路

直接枚举判断 O n 2 O n^2 On2

约数问题 考虑使用 倍数 做优化

在值域 1 − N 1-N 1−N中,考虑如果 j j j存在,那么我们就令 r e s [ j ] + = c n t [ i ] res[j] +=cnt[i] res[j]+=cnt[i]

时间复杂度 O N l o g N ONlogN ONlogN

Mycode

void solve()
{
	cin>>n;
	for(int i=1;i>a[i];cnt[a[i]]++;}
	for(int i =  0 ; i