Codeforces Round 954 (Div. 3) G2. Permutation Problem (Hard Version)（数论）

题目

给定n(n<=5e5)的排列p，求满足pi*pj是i*j倍数的(i,j)对数

实际t(t<=1e4)组数据，保证sumn不超过5e5

思路来源

propane(cup_pyy)代码

题解

pi*pj=k*i*j

(pi/i)*(pj/j)=k，比如，(4/3)*(9/2)=6，

一定存在pi的约数x、pj的约数y满足(2/3)*(3/2)=1

暴力这么做是一个log一个约数个数d(n)的

这个时间复杂度应该可以过G2，但是这个G2卡空间，写map会mle43，手写哈希也卡不过

参考了一些选手的写法，写成了倍数枚举的形式

代码1（MLE）

朴素想法，时间复杂度是对的，

可以过G1，但是会在G2上MLE

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
//(pi/i)*(pj/j)=k
//(4/5)*(15/4)=3
//(4/3)*(6/2)=4
//(2/3)*(3/2)=1
const int N=5e5+10;
int t,n,p[N];
map<P,int>mp;
vector<int>fac[N];
int gcd(int x,int y){return !y?x:gcd(y,x%y);}
int main(){
    for(int i=1;i<N;++i){
        for(int j=i;j<N;j+=i){
            fac[j].pb(i);
        }
    }
    sci(t);
    while(t--){
        sci(n);
        ll ans=0;
        mp.clear();
        rep(i,1,n){
            sci(p[i]);
            int x=p[i],y=i,g=gcd(x,y);
            x/=g,y/=g;
            for(auto &v:fac[x]){//y/x
                if(mp.count({y,v})){
                    ans+=mp[{y,v}];
                }
            }
            for(auto &v:fac[x]){//x/y
                mp[{v,y}]++;
            }
        }
        ptlle(ans);
    }
    return 0;
}

代码2

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
//(pi/i)*(pj/j)=k
//(4/5)*(15/4)=3
//(4/3)*(6/2)=4
//(2/3)*(3/2)=1
const int N=5e5+10;
int t,n,p,now[N];
vector<int>ask[N],add[N],fac[N];
int gcd(int x,int y){return !y?x:gcd(y,x%y);}
int main(){
    for(int i=1;i<N;++i){
        for(int j=i;j<N;j+=i){
            fac[j].pb(i);
        }
    }
    sci(t);
    while(t--){
        sci(n);
        ll ans=0;
        rep(i,1,n){
            ask[i].clear();
            add[i].clear();
        }
        rep(i,1,n){
            sci(p);
            int x=p,y=i,g=gcd(x,y);
            x/=g,y/=g;
            if(y==1)ans--;//减去自己
            ask[y].pb(x);//ans+=mp[(y,v)] v是x约数
            add[x].pb(y);//mp[(v,y)]++ v是x约数
        }
        rep(i,1,n){
            for(int j=i;j<=n;j+=i){
                for(auto &y:add[j]){
                    now[y]++;
                }
            }
            for(auto &x:ask[i]){
                for(auto &v:fac[x]){
                    ans+=now[v];
                }
            }
            for(int j=i;j<=n;j+=i){
                for(auto &y:add[j]){
                    now[y]--;
                }
            }
        }
        ptlle(ans/2);
    }
    return 0;
}