結果

問題 No.2849 Birthday Donuts
ユーザー kotatsugamekotatsugame
提出日時 2024-08-23 22:35:08
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
6,816 KB
testcase_01 AC 6 ms
6,812 KB
testcase_02 AC 2,063 ms
6,944 KB
testcase_03 AC 2,084 ms
6,944 KB
testcase_04 AC 1,940 ms
6,940 KB
testcase_05 AC 1,975 ms
6,940 KB
testcase_06 AC 1,983 ms
6,940 KB
testcase_07 AC 2,034 ms
6,944 KB
testcase_08 AC 1,981 ms
6,940 KB
testcase_09 AC 1,961 ms
6,940 KB
testcase_10 AC 2,004 ms
6,944 KB
testcase_11 AC 2,022 ms
6,944 KB
testcase_12 AC 1,783 ms
6,940 KB
testcase_13 AC 1,825 ms
6,940 KB
testcase_14 AC 1,897 ms
6,940 KB
testcase_15 AC 1,840 ms
6,940 KB
testcase_16 AC 1,973 ms
6,940 KB
testcase_17 AC 1,779 ms
6,940 KB
testcase_18 AC 1,955 ms
6,940 KB
testcase_19 AC 1,820 ms
6,940 KB
testcase_20 AC 1,843 ms
6,940 KB
testcase_21 AC 112 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

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