QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#83355 | #3241. 最小公倍树 | fengyuyue | AC ✓ | 132ms | 8132kb | C++14 | 2.7kb | 2023-03-01 16:00:25 | 2023-03-01 16:00:26 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
#define gc getchar
#define pc putchar
#define pii pair<int,int>
#define For(i,l,r) for(int i=(l);i<=(r);i++)
#define for_son(u) for(int e=head[u];e;e=nxt[e])
#define eps (1e-8)
#define INF 0x3f3f3f3f
using namespace std;
char aa;
namespace ljh
{
namespace IO
{
const int SIZ=1<<20;
char ibuf[SIZ],*p1,*p2,obuf[SIZ],*p3=obuf;
// #define gc() (p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,SIZ,stdin),p1==p2)?EOF:*p1++)
// il void pc(const char &c)
// {
// if(p3-obuf==SIZ) fwrite(obuf,1,SIZ,stdout),p3=obuf;
// *p3++=c;
// }
inline int rd()
{
int x=0,f=1;
char ch=gc();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=gc();
}
while(isdigit(ch)){
x=x*10+ch-'0';
ch=gc();
}
return x*f;
}
inline void wr(int x,char ch)
{
if(x<0) x=-x,pc('-');
static char st[12];
int top=0;
do{
st[top++]=x%10+'0',x/=10;
}while(x);
while(top) pc(st[--top]);
pc(ch);
}
inline ll ll_rd()
{
ll x=0;
int f=1;
char ch=gc();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=gc();
}
while(isdigit(ch)){
x=x*10+ch-'0';
ch=gc();
}
return x*f;
}
inline void ll_wr(ll x,char ch)
{
if(x<0) x=-x,pc('-');
static char st[22];
int top=0;
do{
st[top++]=x%10+'0',x/=10;
}while(x);
while(top) pc(st[--top]);
pc(ch);
}
inline int qpow(int a,int b,int p)
{
a%=p;
int res=1;
while(b){
if(b&1) res=1ll*res*a%p;
a=1ll*a*a%p;
b>>=1;
}
return res;
}
// inline void add_edge(int u,int v)
// {
// nxt[++cnt]=head[u];
// to[cnt]=v;
// head[u]=cnt;
// }
}
using namespace IO;
const int N=1e5+5,mod=0;
struct Node{
int d,u,v;
ll val;
};
struct cmp{
bool operator () (const Node &a,const Node &b)
{
return a.val>b.val;
}
};
int n,L,R,fa[N];
ll ans;
priority_queue<Node,vector<Node>,cmp>q;
int get(int x)
{
return fa[x]==x?x:fa[x]=get(fa[x]);
}
void main()
{
L=rd(),R=rd(),n=R-L+1;
For(i,1,n) fa[i]=i;
For(d,1,n){
int st=(L+d-1)/d*d;
if(st+d<=R) q.push(Node{d,st,st+d,1ll*st/d*st+st});
}
while(!q.empty())
{
Node t=q.top();
q.pop();
int d=t.d,u=t.u,v=t.v;
ll val=t.val;
int su=get(u-L+1),sv=get(v-L+1);
if(su!=sv) fa[su]=sv,ans+=val;
if(v+d<=R) q.push((Node){d,u,v+d,val+u});
}
ll_wr(ans,'\n');
// fwrite(obuf,1,p3-obuf,stdout);
}
/*
*/
}
char bb;
int main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
ljh::main();
// cerr<<(&bb-&aa)/1024/1024<<endl;
// fclose(stdin);
// fclose(stdout);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 75ms
memory: 8132kb
input:
100000 200000
output:
171167496763057
result:
ok single line: '171167496763057'
Test #2:
score: 0
Accepted
time: 61ms
memory: 6348kb
input:
253276 353266
output:
927665531658996
result:
ok single line: '927665531658996'
Test #3:
score: 0
Accepted
time: 61ms
memory: 6384kb
input:
655914 755442
output:
5580601534791953
result:
ok single line: '5580601534791953'
Test #4:
score: 0
Accepted
time: 70ms
memory: 6340kb
input:
900000 1000000
output:
10250678499914055
result:
ok single line: '10250678499914055'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3240kb
input:
99991 99991
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 70ms
memory: 6432kb
input:
99991 199982
output:
171132525371252
result:
ok single line: '171132525371252'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3184kb
input:
100003 100003
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3396kb
input:
666666 666667
output:
444444222222
result:
ok single line: '444444222222'
Test #9:
score: 0
Accepted
time: 132ms
memory: 4892kb
input:
1 99667
output:
4966805277
result:
ok single line: '4966805277'
Test #10:
score: 0
Accepted
time: 132ms
memory: 4988kb
input:
2 99248
output:
5373052945
result:
ok single line: '5373052945'
Test #11:
score: 0
Accepted
time: 63ms
memory: 6304kb
input:
798954 898945
output:
8177721171091522
result:
ok single line: '8177721171091522'