結果

問題 No.2849 Birthday Donuts
コンテスト
ユーザー kotatsugame
提出日時 2024-08-23 22:35:08
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,084 ms / 6,000 ms
コード長 644 bytes
コンパイル時間 591 ms
コンパイル使用メモリ 66,032 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-08-23 22:35:49
合計ジャッジ時間 39,438 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<cassert>
using namespace std;
int phi[2<<17];
long S[2<<17];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	for(int p=2;p<2<<17;p++)phi[p]=p;
	for(int p=2;p<2<<17;p++)if(phi[p]==p)
	{
		for(int j=p;j<2<<17;j+=p)phi[j]=phi[j]/p*(p-1);
	}
	for(int p=2;p<2<<17;p++)S[p]=S[p-1]+phi[p];
	int T;cin>>T;
	long prv=0;
	for(;T--;)
	{
		int L,R;
		{
			long a,b;
			cin>>a>>b;
			L=a^prv;
			R=b^prv;
		}
		L--;
		long ans=0;
		int a=2;
		while(a<=R)
		{
			int qR=R/a;
			int qL=L/a;
			int ra=R/qR;
			if(qL>0)ra=min(ra,L/qL);
			if(qL<qR)ans+=S[ra]-S[a-1];
			a=ra+1;
		}
		cout<<ans<<"\n";
		prv=ans;
	}
}
0