QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#83355#3241. 最小公倍树fengyuyueAC ✓132ms8132kbC++142.7kb2023-03-01 16:00:252023-03-01 16:00:26

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-01 16:00:26]
  • 评测
  • 测评结果:AC
  • 用时:132ms
  • 内存:8132kb
  • [2023-03-01 16:00:25]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'