思路:首先最外層是動(dòng)態(tài)規(guī)劃,cnt[k]=cnt[k-1]+m;這里cnt[k]是k計(jì)算result,tmp是(i+k)/gcd(i,k)累加,其中i屬于[1,k-1];然后說(shuō)一下怎么求tmp,tmp對(duì)于k為質(zhì)數(shù)和合數(shù)有不同的求法。如果k是質(zhì)數(shù),m的結(jié)果是(k)*(k-1)*3/2;而如果k不是質(zhì)數(shù),先假設(shè)它是質(zhì)數(shù),然后減去一個(gè)數(shù)dif。說(shuō)一下怎么求dif,對(duì)于所有比根號(hào)k小且被k整除的質(zhì)數(shù)j,有k/j=c;則合數(shù)是由質(zhì)數(shù)的j*(1+2+...c-1)*(c*j)/1變成了j(1+2+...c-1)*(c*j)/j,也就是(1+2+...c-1)*(c*j),相比質(zhì)數(shù)少了(j-1)(1+2+....