problem1 link
枚举指数，然后判断是不是素数即可。
problem2 link
令$f[len][a][b][r]$(r=0或者1)表示子串$init[a,a+len-1]$匹配$goal[b,b+len-1]$,翻转了$r$次的最小代价。
problem3 link
答案的公式很容易推导，为$n*sum_{i=n-k+1}^{n}frac{1}{i}$.
调和级数为$H(n)=sum_{i=1}^{n}frac{1}{i}$
所以答案为$n*(H(n)-H(n-k))$
由于$n$较大，不能枚举，这里有它的近似公式：
$frac{1}{24(n+1)^{2}}<H(n)-ln(n+frac{1}{2})-gamma<frac{1}{24n^{2}}$
所以$H(n)-H(n-k)approx ln(frac{n+frac{1}{2}}{n-k+frac{1}{2}})=ln(frac{2n+1}{2n-2k+1})$
所以对于$H(n)$的较小部分暴力，然后用近似公式。
code for problem1
import java.util.*;
import java.math.*;
import static java.lang.Math.*;
public class StrongPrimePower {
public int[] baseAndExponent(String n) {
final long m=Long.valueOf(n);
for(int i=2;i<=60;++i) {
final int k=cal(i,m);
if(k==-1) {
continue;
}
if(isprime(k)) {
return new int[]{k,i};
}
}
return new int[0];
}
int cal(int k,long m) {
int low=1,high=(int)Math.sqrt(m)+1;
int result=1;
while(low<=high) {
int mid=(low+high)>>1;
if(pow(mid,k,m)>m) {
high=mid-1;
}
else {
result=Math.max(result,mid);
low=mid+1;
}
}
if(pow(result,k,m)==m) {
return result;
}
return -1;
}
long pow(long a,long b,long n) {
long result=1;
while(b>0) {
if(1==(b&1)) {
if(result>n/a) {
return n+1;
}
result*=a;
if(b==1) {
return result;
}
}
if(a>n/a) {
return n+1;
}
a=a*a;
b>>=1;
}
return result;
}
boolean isprime(int n) {
if(n==1) {
return false;
}
for(long i=2;i*i<=n;++i) {
if(n%i==0) {
return false;
}
}
return true;
}
}
code for problem2
import java.util.*;
import java.math.*;
import static java.lang.Math.*;
public class ReversalChain {
static final int INF=10000000;
String init=null;
String goal=null;
int n;
int[][][][] f=null;
public int minReversal(String init,String goal) {
this.init=init;
this.goal=goal;
n=init.length();
f=new int[n+1][n][n][2];
for(int i=0;i<n+1;++i) {
for(int j=0;j<n;++j) {
for(int k=0;k<n;++k) {
for(int t=0;t<2;++t) {
f[i][j][k][t]=-1;
}
}
}
}
int result=dfs(n,0,0,0);
if(result>=INF) {
return -1;
}
return result;
}
int dfs(int len,int a,int b,int t) {
if(len==0) {
return 0;
}
if(len==1) {
return init.charAt(a)==goal.charAt(b)?0:INF;
}
if(f[len][a][b][t]!=-1) {
return f[len][a][b][t];
}
f[len][a][b][t]=INF;
if(t==0) {
if(init.charAt(a)==goal.charAt(b)) {
f[len][a][b][t]=Math.min(f[len][a][b][t],dfs(len-1,a+1,b+1,0));
}
if(init.charAt(a+len-1)==goal.charAt(b+len-1)) {
f[len][a][b][t]=Math.min(f[len][a][b][t],dfs(len-1,a,b,0));
}
if(init.charAt(a)==goal.charAt(b+len-1)) {
f[len][a][b][t]=Math.min(f[len][a][b][t],dfs(len-1,a+1,b,1)+1);
}
if(init.charAt(a+len-1)==goal.charAt(b)) {
f[len][a][b][t]=Math.min(f[len][a][b][t],dfs(len-1,a,b+1,1)+1);
}
}
else {
if(init.charAt(a)==goal.charAt(b)) {
f[len][a][b][t]=Math.min(f[len][a][b][t],dfs(len-1,a+1,b+1,0)+1);
}
if(init.charAt(a+len-1)==goal.charAt(b+len-1)) {
f[len][a][b][t]=Math.min(f[len][a][b][t],dfs(len-1,a,b,0)+1);
}
if(init.charAt(a)==goal.charAt(b+len-1)) {
f[len][a][b][t]=Math.min(f[len][a][b][t],dfs(len-1,a+1,b,1));
}
if(init.charAt(a+len-1)==goal.charAt(b)) {
f[len][a][b][t]=Math.min(f[len][a][b][t],dfs(len-1,a,b+1,1));
}
}
return f[len][a][b][t];
}
}
code for problem3
import java.util.*;
import java.math.*;
import static java.lang.Math.*;
public class CollectingBonuses {
final static int LIMIT=10000000;
public double expectedBuy(String n, String k) {
long nn=Long.valueOf(n);
long mm=Long.valueOf(k);
long m=nn-mm+1;
double result=0;
while(m<=LIMIT) {
result+=1.0/m;
if(m==nn) {
return nn*result;
}
++m;
}
result+=Math.log1p((2*nn-2*m+2.0)/(2.0*m-1));
return nn*result;
}
}