首页 > 其他分享 >[gym102770L]List of Products

[gym102770L]List of Products

时间:2023-07-15 22:00:21浏览次数:35  
标签:ch int gym102770L List times Products 我们 id leqslant

题意简述

我们根据唯一分解定理得到,对于每一个数 \(x\) 可以表示成 \(\sum p_i^{e_i}\) 的形式,其中 \(p_i\) 表示第 \(i\) 大的素数。
我们重新定义两个数之间的比较,对于两个数 \(x,y\) :

  • 如果 \(x=y\) ,两个数相等

  • 如果 \(x,y\) 不相等,我们就从小到大枚举素数,知道找到一个下标 \(j\) 满足对于 \(i<j\) 两个数的 \(e_i\) 相等,但是 \(e_j\) 不相等。\(e_j\) 大的更大。比如 \(2>7\) 。

我们现在有两个序列,长度分别为 \(n,m\) 。我们将两个序列的 \((i,j)\) 变成 \(a_i\times b_j\) 放入一个新的序列 \(c\) 。问我们将 \(c\) 从小到大排序后,第 \(k\) 个数是多少。 \(n,m \leqslant 1e5,k \leqslant nm\) 。

思路点拨

我们考虑到一个性质: \(a \leqslant x\) 并且 \(b \leqslant y\) ,就会有 \(ab \leqslant xy\) 。这个结论显然但是重要。

因为 \(k\) 个数我们枚举是不可行的,所以我们考虑二分这个答案。对于 \(a_i \times b_j\) ,我们该如何计数?我们可以在序列 \(a\) 中枚举一个 \(id_i\) ,在序列 \(b\) 中找到 \(id_j\) 使得 \(a_{id_i}\times a_{id_j}\) 是尽量接近 \(a_i\times b_j\) 的。由于我们刚刚的性质,可以知道,在 \(id_i\) 不断变大的过程中, \(id_j\) 会渐渐变小。我们双指针可以求出这个答案。

但是实际上,在二分的过程中我们需要选择一个节点 \(mid\) 来比较,但是这题中这个点并不好找。我们考虑一个区间 \([l,r]\) ,注意,这个区间并不是一个连续的区间,因为题解中的大小是按照题目规定来的。那么我们可以找到有多少个 \((i,j)\) 有 \(l < a_i \times a_j <r\) ,在这些点中随机一个值,这样的期望时间和二分是一样的。但是这个值怎么找呢?

还是利用单调性。这一点可以留给读者自己思考。

代码

原题对常数的要求比较严格,我的这份代码并不可以通过,仅供参考:

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-f;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
const int MAXN=5e5+10;
int n,m,k;
struct node{
	vector<int> p;//质因子
	void clear(){p.clear();}
	bool friend operator<(const node &A,const node &B){
		int len=min(A.p.size(),B.p.size());
		for(int i=0;i<len;i++){
			if(A.p[i]==B.p[i]) continue;
			else return A.p[i]>B.p[i];
		}
		return A.p.size()<B.p.size();
	} 
	bool friend operator==(const node &A,const node &B){
		if(A.p.size()!=B.p.size())
			return 0;
		int len=A.p.size();
		for(int i=0;i<len;i++){
			if(A.p[i]==B.p[i]) continue;
			return 0;
		}
		return 1;
	}
	bool friend operator>=(const node &A,const node &B){
		if(A<B) return 0;
		return 1;
	}
}temp;
node merge(node x,node y){
    temp.p.clear();
    for(int i=0,j=0;(i<x.p.size())||(j<y.p.size());)
        if ((i!=x.p.size())&&((j==y.p.size())||(x.p[i]<y.p[j])))temp.p.push_back(x.p[i++]);
        else temp.p.push_back(y.p[j++]);
    return temp;
}
const int N=1e6;
int vis[N+10];
vector<int> o[N];
void init(){
	for(int i=2;i<=N;i++){
		if(vis[i]) continue;
		o[i].push_back(i);
		for(int j=i*2;j<=N;j+=i){
			vis[j]=1;
			o[j].push_back(i);
		}
	}
}
node a[MAXN],b[MAXN];
node split(int x){
	temp.clear();
	int y=x;
	for(int i=0;i<o[x].size();i++){
		while(y%o[x][i]==0){
			temp.p.push_back(o[x][i]);
			y/=o[x][i];
		}
	}
	return temp;
}
int ft[MAXN],ed[MAXN];
int run(node k){
    int ans=0;
    for(int i=1,j=m;i<=n;i++){
        while (j&&(k<merge(a[i],b[j]))) j--;
        int s_i=i,s_j=j;
        while (j&&(k==merge(a[s_i],b[j]))) j--;
        while (i&&(k==merge(a[i],b[s_j]))) i++;
        ans+=(i-s_i)*(s_j-j);
    }
    return ans;
}
int fun(node A){
	int ans=0;
	for(int l=1,r=m;l<=n;l++){
		while(r&&A<merge(a[l],b[r]))
			r--;
		ans+=r;
	}
	return ans;	
}
int solve(){
	node L=merge(a[1],b[1]),R=merge(a[n],b[m]);
	while(1+1==2){
		ft[0]=ed[0]=m;
		int useful=0;//在二分的值域内存在的有用点对 
		for(int i=1;i<=n;i++){
			ft[i]=ft[i-1],ed[i]=ed[i-1];
			while(ft[i]>1&&!(merge(a[i],b[ft[i]-1])<L)) ft[i]--;
			while(ed[i]&&R<merge(a[i],b[ed[i]])) ed[i]--;
			useful+=(ed[i]-ft[i]+1);
		}
		if(useful==run(L)+run(R)) break;//此时[l,r]之间没有除了l,r之外的决策点
		int kk=rand()%useful+1,l,r;
		for(int i=1;i<=n;i++){
			if(ed[i]-ft[i]+1<kk)
				kk-=(ed[i]-ft[i]+1);
			else{
				l=i;
				r=ft[i]+kk-1;
				break;
			} 
		}
		node mid=merge(a[l],b[r]);
		if(fun(mid)<=k) L=mid;
		else R=mid;
	}
	int cnt=1;
	for(int i=0;i<L.p.size();i++) cnt*=L.p[i];
	return cnt;
}
signed main(){
	srand(time(0));
	int T=read();
	init();//筛法
	while(T--){
		n=read(),m=read(),k=read();
		for(int i=1;i<=n;i++){
			int x=read();
			a[i]=split(x);
		}
		for(int i=1;i<=m;i++){
			int x=read();
			b[i]=split(x);
		}	
		sort(a+1,a+n+1);
		sort(b+1,b+m+1);
		cout<<solve()<<endl;
	} 
	return 0;
}

标签:ch,int,gym102770L,List,times,Products,我们,id,leqslant
From: https://www.cnblogs.com/Diavolo/p/17557059.html

相关文章

  • antd table提示Warning: Each child in a list should have a unique "key" prop.
    参考:表中的每条记录都应该有一个唯一的“key”属性,或者将“rowKey”设置为唯一的主键。·问题#7623·ant-design/ant-design解决<Tablecolumns={columns}dataSource={this.props.categories}rowKey="name"/>原因:column没有指定key,那就在表中指定下其他解......
  • python 多层list遍历
    Python多层列表遍历指南作为一名经验丰富的开发者,我很高兴能够帮助你学习如何在Python中实现多层列表的遍历。在本篇文章中,我将向你介绍整个遍历过程的流程,并为每一步提供相应的代码示例和注释。目录准备工作多层列表的遍历方法示例代码总结1.准备工作在开始之前,确保......
  • pythonlist添加一行
    PythonList添加一行的实现方法一、整体流程为了帮助刚入行的小白理解如何实现“PythonList添加一行”,我们可以使用以下步骤进行解释:步骤描述1创建一个空的列表2定义要添加的新行3使用列表的append()方法将新行添加到列表中4打印列表以验证添加的行......
  • Spartacus Product List Page ProductSearchPage Observable 对象的设计明细
    源代码如下:readonlymodel$:Observable<ProductSearchPage>=using(()=>this.searchByRouting$.subscribe(),()=>this.searchResults$).pipe(shareReplay({bufferSize:1,refCount:true}));上面这段代码是基于Angular框架和RxJS库的,RxJS是一个用于处理......
  • 关于 Spartacus ProdutList Component Service model$ 的填充逻辑
    源代码:这段代码是Angular中的RxJS代码,主要是创建一个名为model$的Observable对象,这个对象的生成逻辑复杂一些,主要涉及using,subscribe,pipe,shareReplay等函数的使用。逐行解释如下:readonlymodel$:Observable<ProductSearchPage>=using(这一行定义了一个......
  • cpp class constructor initialize list and override cout
    //book.h#pragmaonce#include<iostream>classbook{public:intidx;std::uint64_tid;std::stringauthor;std::stringcontent;std::stringcomment;std::stringisbn;std::stringsummary;std::stringtopic;boo......
  • Python - list VS tuple, list() VS []
    差异一:list可变vstuple不可变列表是动态的,长度大小不固定,可以随意地增加、删减或者改变元素(mutable)。而元组是静态的,长度大小固定,无法增加删减或者改变(immutable)。#Jupyter格式tup=(1,2,3,4)new_tup=tup+(5,)#创建新的元组new_tup,并依次填充原元组的值new_......
  • dede织梦标签,dede:arclist用法与详解
    标签名称:arclist标记简介:织梦常用标记,也称为自由列表标记,其中imglist、imginfolist、specart、coolart、autolist都是由该标记所定义的不同属性延伸出来的别名标记。功能说明:获取指定文档列表适用范围:全局使用基本语法:{dede:arclist?flag='h'typeid=''row=''col=''titlelen=......
  • java获取list类类型
    Java获取List类类型在Java中,要获取List的类类型可以通过以下步骤来实现。在本文中,我将详细介绍每个步骤以及使用的代码。步骤步骤描述步骤1创建一个List对象步骤2获取List对象的类类型步骤1:创建一个List对象首先,我们需要创建一个List对象,我们可以使用ArrayLi......
  • java获取list的type
    Java获取List的Type在Java中,List是一种常用的数据结构,用于存储一组有序的元素。有时候我们需要获取List中元素的类型,以便进行一些操作或判断。本文将介绍几种获取List类型的方法,并提供相应的代码示例。方法一:通过泛型参数获取类型在Java中,我们可以使用泛型来定义List的类型。通......