社区讨论

为何无法通过

UVA1718 Tile Cutting参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@ltpgirvn
此快照首次捕获于
2024/03/13 15:05
2 年前
此快照最后确认于
2024/03/13 17:37
2 年前
查看原帖
在双倍经验P6913都过了,但是这里直接 WA #1
CPP
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set> 
#include <map>
#include <bitset>
#include <cmath>
#define int long long
using namespace std; 

const double pi=acos(-1);
void read(int &x){
	x=0;
	int f=1;
	char c=getchar();
	while(!('0'<=c && c<='9')){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while('0'<=c && c<='9'){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	x*=f;
}
struct Complex{
	double r,i;
	Complex(){
		r=i=0;
	}
	Complex(int k){
		r=k;
		i=0;
	}
	Complex(double rr,double ii){
		r=rr;
		i=ii;
	}
	friend Complex operator+(Complex a,Complex b){
		return Complex(a.r+b.r,a.i+b.i);
	}
	friend Complex operator-(Complex a,Complex b){
		return Complex(a.r-b.r,a.i-b.i);
	}
	friend Complex operator*(Complex a,Complex b){
		return Complex(a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r);
	}
} f[1100010];
int flp[2100010];
void flip(Complex *f,int n){
	for(int i=1;i<n;i++){
		flp[i]=flp[i>>1]>>1;
		if(i&1){
			flp[i]|=(n>>1);
		}
		if(flp[i]<i){
			swap(f[flp[i]],f[i]);
		}
	}
}
void ntt(Complex *f,int n,bool is){
	flip(f,n);
	for(int i=1;i<n;i<<=1){
		Complex rt=is?Complex(cos(pi/i),sin(pi/i)):Complex(cos(pi/i),-sin(pi/i));
		for(int j=0;j<n;j+=(i<<1)){
			Complex cur(1);
			for(int k=0;k<i;k++){
				Complex x=f[j+k],y=f[i+j+k]*cur;
				f[j+k]=x+y;
				f[i+j+k]=x-y;
				cur=cur*rt;
			}
		}
	} 
}
int t,l,r,sum[500010]={0};
signed main(){
	for(int i=1;i<=500000;i++){
		for(int j=i;j<=500000;j+=i){
			sum[j]++;
		}
	}
	for(int i=1;i<=500000;i++){
		f[i]=sum[i];
	}
	ntt(f,1<<20,1);
	for(int i=0;i<(1<<20);i++){
		f[i]=f[i]*f[i];
	}
	ntt(f,1<<20,0);
	for(int i=1;i<=500000;i++){
		sum[i]=round(f[i].r/(1<<20))+0.5;
	}
	read(t);
	while(t--){
		read(l);
		read(r);
		int mx=0,mxi;
		for(int i=l;i<=r;i++){
			if(sum[i]>=mx){
				mx=sum[i];
				mxi=i;
			}
		}
		printf("%lld %lld\n",mxi,mx);
	}
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...