最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

天天讯息：Atcoder Beginner Contest ABC 283 Ex Popcount Sum 题解 (类欧几里得算法)

来源：博客园


(资料图)

题目链接

令\(p=\lfloor\frac{n-r}m\rfloor\)，则我们其实是要对所有\(0\le i \le 29\)求\(\sum_{j=0}^p (\lfloor \frac{mj+r}{2^i}\rfloor mod \ 2)\)。右边那个东西如果没有那个\(mod\ 2\)，其实就是类欧几里得算法的最基本情况。

关于类欧

顺便说一句，oiwiki的搜索功能问题很大，比如在搜索框直接搜类欧根本搜不到。

进一步观察发现，如果我们能对每个\(0\le i\le 29\)求出\(\sum_{j=0}^p \lfloor \frac{mj+r}{2^i}\rfloor\)，其实也已经能计算答案了。令在\(i\)时求出的右边式子的值为\(f_i\)。则对于任意i，在\(f_i\)中，每个第i位的1都被计算了1次，每个第i+1位的1都被计算了2次，……，每个第j位的1都被计算了\(2^{j-i}\)次。令\(g_i\)表示实际上第i位的1的总个数，则\(g_i=f_i-\sum_{j>i}2^{j-i}g_j\)。

总复杂度\(O(tlog^2n)\)。

点击查看代码
#include #define rep(i,n) for(int i=0;i#define pdd pair #define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){  #ifdef LGS  freopen("in.txt","r",stdin);  freopen("out.txt","w",stdout);  #endif}void termin(){  #ifdef LGS  std::cout<<"\n\nEXECUTION TERMINATED";  #endif  exit(0);}using namespace std;LL f(LL a,LL b,LL c,LL n){  LL add=n*(n+1)/2*(a/c)+(n+1)*(b/c);  a%=c;b%=c;  if(a==0) return add+b/c*(n+1);  LL m=(a*n+b)/c;  LL ret=n*m-f(c,c-b-1,a,m-1);  ret+=add;  return ret;}LL t,n,m,r,val[40];int main(){  fileio();  cin>>t;  rep(tn,t)  {    cin>>n>>m>>r;    rep(i,35) val[i]=0;    LL mxi=(n-r)/m;    rep(i,30) val[i]=f(m,r,1LL<=0;--i)    {      for(int j=i+1;j<=29;++j) val[i]-=val[j]*(1LL<<(j-i));      ans+=val[i];    }    printf("%lld\n",ans);  }  termin();}

关键词： 欧几里得算法 点击查看