首页 > 其他分享 >ABC 249 D - Index Trio(暴力/倍增)

ABC 249 D - Index Trio(暴力/倍增)

时间:2022-10-05 11:55:08浏览次数:77  
标签:Index Trio ABC LL cin Sample maxn Output Input

https://atcoder.jp/contests/abc249/tasks/abc249_d

题目大意:

给定n个数字,问我们能够满足Ai/Aj==Ak的数量有多少?

i,j,k只需要在下标的范围内即可,无硬性要求。
Sample Input 1 
3
6 2 3
Sample Output 1 
2
(i,j,k)=(1,2,3),(1,3,2) satisfy the conditions.

Sample Input 2 
1
2
Sample Output 2 
0

Sample Input 3
10
1 3 2 4 6 8 2 2 3 7
Sample Output 3
62
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=200200,M=2002;
LL a[N];
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        LL n;
        cin>>n;
        map<LL,LL> mp;
        LL maxn=0;
        for(LL i=1;i<=n;i++)
        {
            cin>>a[i];
            maxn=max(maxn,a[i]);
            mp[a[i]]++;
        }
        LL res=0;
        for(LL i=1;i<=maxn;i++)//从小到大枚举出现过的数字
        {
            for(LL j=1;j*i<=maxn;j++)//然后倍增,把所有可以乘起来且有结果的数量加起来
            {
                LL k=i*j;
                res+=mp[i]*mp[j]*mp[k];
                //Ai/Aj==Ak可以相应的转化成Ai*Aj==Ak
                //这样我们直接计算彼此的乘积即为答案
            }
        }
        cout<<res<<endl;
        mp.clear();
    }
    return 0;
}

标签:Index,Trio,ABC,LL,cin,Sample,maxn,Output,Input
From: https://www.cnblogs.com/Vivian-0918/p/16755333.html

相关文章

  • ABC267Ex - Odd Sum
    分治NTTEx-OddSum(atcoder.jp)题意给一个长度为\(n\;(1<=n<=10^5)\)的数组\(A\;(A[i]<=10)\),给定\(M\;(1<=M<=10^6)\),求在\(A\)中选奇数个数,满足它们的......
  • ABC264
    ABC264VPABCDEF50:053:3619:0329:0749:1397:20+1rk:\(471st\)perf:\(\color{Blue}{1843}\)Asubser(x,y),输出string类型的\(x\)位......
  • [Typescript] 42. Medium - Remove Index Signature
    Implement RemoveIndexSignature<T> ,excludetheindexsignaturefromobjecttypes.Forexample:typeFoo={[key:string]:any;foo():void;}typeA=......
  • ABC 248 D - Range Count Query(思维)
    https://atcoder.jp/contests/abc248/tasks/abc248_d题目大意:给定一个长度为n的数组a,再给出q次询问;每次询问都问我们区间a[l]~a[r]中k的出现次数是多少?SampleInput......
  • ABC 248 C - Dice Sum(DP:背包)
    https://atcoder.jp/contests/abc248/tasks/abc248_c题目大意:给定长度为n,可选择的数字的范围【1,m】,放置的数字的总和不能超过k;问我们能凑出多少种不同的情况?取模。......
  • ABC 246 D - 2-variable Function(数论/暴力)
    https://atcoder.jp/contests/abc246/tasks/abc246_d题目大意:给定一个数字N,让我们求出X,这个X要满足X>=N,并且X内部可以有一对(a,b)满足a^3+a^2*b+b^2*a+b^3。找出最......
  • ABC 246 C - Coupon(思维)
    怎么最近连纯思维题都写不出来了???我人傻了https://atcoder.jp/contests/abc246/tasks/abc246_c题目大意:给定n个价钱,我们手里有k个优惠卷,每个优惠卷都可以减7元;假如......
  • ABC-270 F - Transportation(kruskal)
    ABC-270F-Transportation(kruskal)考虑等价转换,建立两个虚点(分别表示airport和harbor的中转站)。这样就可以把点统一为边权问题。对于操作1和操作2,就是等价于向虚点连边......
  • solution-arc149(ABC)
    A就是枚举,先枚举是哪个数再枚举位数。把这种题放arcA感觉挺没意思。#include<cstdio>usingnamespacestd;intansx,ansy;voidcheckmax(inti,intj){if(......
  • cisco 设备 index 重启后是否发生变化
    跟思科确认:用asr1001-x路由器开的case。思科售后通过用真机测试,可以确定,asr路由器的index重启后会重新排列,此机制是无法改变的。3750交换机index不会改变,因为每一个index......