TopCoder SRM 691 Div2 Hard Undiv2

ちょっと手間取った。
https://community.topcoder.com/stat?c=problem_statement&pm=14294

問題

正整数xに対し、f(x)とはxを割り切らない正整数のうち２番目に小さいものを言う。
正整数nに対し、f(1)～f(n)の和を求めよ。

解法

ためしにf(n)の最大値を求めると、n≦10^9の範囲では25が最大である。
g(a,b,n) := n以下の整数xで、xを割り切らない最初と２番目の正整数がaとbであるものの数
とする。解はとなる。
あとはg(a,b,n)を求めよう。

a,bに対し、v:= 1～(b-1)からaを除いたもののLCM とする。
a,bのいずれかがvの約数である場合、g(a,b,n)=0である。
以下、それ以外の場合を考える。

a' := GCD(a,v)
b' := GCD(b,v)
とする。
g(a,b,n)に含まれるxはvの倍数であり、かつx/vがa'やb'の倍数でないものを列挙すればよい。
すなわち、p = n/vとすると、p以下のa'とb'どちらの倍数でもない数を数えればそれがg(a,b,n)。

class Undiv2 {
	public:
	
	long long getsum(int n) {
		int y,x,i;
		ll ret=0;
		for(y=1;y<=26;y++) for(x=1;x<y;x++) {
			ll v=1;
			ll x2=x,y2=y;
			for(i=1;i<y;i++) if(i!=x) v*=i/__gcd(v,(ll)i);
			x2/=__gcd(v,(ll)x);
			y2/=__gcd(v,(ll)y);
			if(v<=n) {
				int num[26*26]={};
				for(i=1;i<=x2*y2;i++) num[i]=num[i-1]+(((i%y2)>0)&&((i%x2)>0));
				ll di=n/v;
				ret += y*(di/(x2*y2)*num[x2*y2] + num[di%(x2*y2)]);
			}
		}
		
		return ret;
		
	}
}

まとめ

ちょっと迷ったけど解けて良かった。