如何做网站 写代码,苏州网站建设找哪家,网站开发工程师岗位职责要求,手机上怎么查看网站设计d数组是来算#xff08;x整除y#xff09;*y中y比x小的数 s数组是算#xff08;x整除y#xff09;*y中y比x大的数
#xff08;x整除y#xff09;*y 看x对于前面大于他的数是枚举#xff0c;对于前面小于他的数是d树状数组储存。
d中 x整除y表示x中有多少个y 所以 … d数组是来算x整除y*y中y比x小的数 s数组是算x整除y*y中y比x大的数
x整除y*y 看x对于前面大于他的数是枚举对于前面小于他的数是d树状数组储存。
d中 x整除y表示x中有多少个y 所以 每个y对于他的倍数都加上y 比如d【y】y d【y*2】y...d【y*n】y当一个比y大的x要求x整除y*y的时候就可以根据d【x】来求
{要还是不明白的话就设y3x10 10/3)*39333 d【3】d【6】d【9】这真的很巧妙。这样每个数字对于他后面的数字的贡献就可以确定了。就是这个意思。}
那样就看代码吧。
#includeiostream
#includecstdio
using namespace std;typedef long long ll;
const int N1e610;
ll d[N],s[N],ans,sum,num; //d s 是上述的意思 void add(ll *x,int k,int p)
{while(kN)x[k]p,kk-k;
}
ll ask(ll *x,int k)
{ll ans0;while(k)ansx[k],k-k-k;return ans;
}int main()
{int n;scanf(%d,n);for(int i0;in;i){scanf(%lld,num);ans1ll*num*isum; sumnum;ans-ask(d,num); //这里是求x整除y*y中 小与num的数 for(int jnum;jnumN;jnum) //枚举num的倍数 {ans-1ll*(ask(s,jnum-1)-ask(s,j-1))*j; //枚举num的倍数 s存的是数量求j-num-1到j-1的数量这段中那个式子等于j add(d,j,num);//到时候不懂再说 }add(s,num,1); //num的数量1 printf(%lld ,ans);}return 0;}
