yukicoder : No.2849 Birthday Donuts

このテクはよく使うね。
https://yukicoder.me/problems/no/2849

問題

整数L,Rが与えられる。
原点を中心として、L≦i≦Rで1≦j＜iとなる整数対(i,j)に対し、半径i,jの円を2つ描いた。
相似な図形を同じ図形とみなしたとき、全部でいくつの図形が書かれるか。

解法

互いに素である整数対(a,b)のうち、条件を満たすものを考える。
これはaの倍数でL以上R以下のものがあればよい。bはaと素なa未満の組み合わせなので、φ(a)個ある。

よって、各クエリに対し、aの倍数がL以上R以下となるもののうちφ(a)の総和を取ればよい。
これは平方分割で行う。
a≦√Rの範囲は、aを総当たりする。
a＞√Rの範囲については、ceil(L/x)≦a≦floor(R/x)となるようなxがあればよいので、xを√R程度まで総当たりし条件を満たすaの区間を求めればよい。

const int MA=202020;
ll tot[MA+1];
ll S[MA+1];
int T;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=MA;i++) tot[i]=i;
	for(i=2;i<=MA;i++) if(tot[i]==i) {
		for(j=i;j<=MA;j+=i) tot[j]=tot[j]/i*(i-1);
	}
	tot[1]=0;
	for(i=1;i<=MA;i++) S[i]=S[i-1]+tot[i];
	
	
	cin>>T;
	ll ret=0;
	while(T--) {
		ll L,R;
		cin>>L>>R;
		L^=ret;
		R^=ret;
		ret=0;
		for(i=1;i<=500;i++) {
			if((L-1)/i!=R/i) ret+=tot[i];
		}
		int pre=500;
		for(i=500;i>=1;i--) {
			int mi=(L+(i-1))/i;
			int ma=R/i;
			if(ma>pre) {
				mi=max(mi,pre+1);
				if(mi<=ma) ret+=S[ma]-S[mi-1];
				pre=ma;
			}
		}
		cout<<ret<<endl;
		
	}
	
}

まとめ

★3～3.5でいい気はする。