社区讨论
为何无法通过
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 条回复,欢迎继续交流。
正在加载回复...