解法ありきで作られた問題っぽいな。
https://codeforces.com/contest/1603/problem/D
問題
整数[L,R]に対し、C(L,R)はL以上R以下の順序なし整数対(i,j)のうち、GCDがL以上となるものを示す。
以下の問いに答えよ。
整数N,Kが与えられる。
初項が0、末尾がKである、N要素の単調増加な整数列X全通りを考える。
それぞれにおいて、C(X[i]+1,X[i+1])の総和の最小値
解法
R<L*2の場合、C(L,R)は1にしかならない。
よって、Xを(0,1,3,7,15,....)とすると取りえずC(a,b)は常にi=jの時だけカウントしてb-a+1となる。
なので、K≧logNの場合、解はN。
Kが18以下の場合、分割統治の要領で分割位置を列挙していこう。
int T; int K,N; ll phi[101010]; ll PS[101010]; ll dp[103030][20]; ll add[303030]; ll sum(int L,int R) { ll ret=0; while(L<=R) { ll nex=min(R,R/(R/L)); ret+=(nex-L+1)*PS[R/L]; L=nex+1; } return ret; } void dfs(int step,int L,int R,int X,int Y) { if(L>R) return; int M=(L+R)/2; int tar=-1; int i; ll CS=sum(X+1,M); for(i=X;i<=min(M-1,Y);i++) { if(dp[i][step-1]+CS<dp[M][step]) { dp[M][step]=dp[i][step-1]+CS; tar=i; } CS-=PS[M/(i+1)]; } dfs(step,L,M-1,X,tar); dfs(step,M+1,R,tar,Y); } void solve() { int i,j,k,l,r,x,y; string s; for(i=1;i<=100000;i++) phi[i]=i; for(i=1;i<=100000;i++) { for(j=i*2;j<=100000;j+=i) phi[j]-=phi[i]; PS[i]=PS[i-1]+phi[i]; } for(i=1;i<=100000;i++) FOR(j,18) dp[i][j]=1LL<<60; for(i=1;i<=17;i++) dfs(i,1,100000,0,100000); cin>>T; while(T--) { cin>>N>>K; if(K>=18) { cout<<N<<endl; } else { cout<<dp[N][K]<<endl; } } }
まとめ
解法ありきな問題すぎるのは余り好きではないな…。