成都网站网站建设,wordpress个人资料页修改,浦东高端网站开发,云南网站seo外包出题人来报个到
正题
题目链接:https://www.luogu.com.cn/problem/P6860 题目大意 p(a,b)1p(a,b)1p(a,b)1当且经当一只走a∗ba*ba∗b矩形的马可以走到棋盘上任何一个点 求∑a1n∑b1np(a,b)\sum_{a1}^n\sum_{b1}^np(a,b)a1∑nb1∑np(a,b) 解题思路
这个马能走到全图的充要…出题人来报个到
正题
题目链接:https://www.luogu.com.cn/problem/P6860 题目大意
p(a,b)1p(a,b)1p(a,b)1当且经当一只走a∗ba*ba∗b矩形的马可以走到棋盘上任何一个点 求∑a1n∑b1np(a,b)\sum_{a1}^n\sum_{b1}^np(a,b)a1∑nb1∑np(a,b) 解题思路
这个马能走到全图的充要条件显然是它能走到(0,1)(0,1)(0,1)。考虑给出(a,b)(a,b)(a,b)求它能否走到(0,1)(0,1)(0,1)
首先如果gcd(x,y)≠1gcd(x,y)\neq 1gcd(x,y)1显然不行
因为走的顺序无所谓将走的路程分成两段一段是(x±a,y±b)(x\pm a,y\pm b)(x±a,y±b)一段是(x±b,y±b)(x\pm b,y\pm b)(x±b,y±b)。
显然对于第一段能走到的点可以表示为(2ax,2ay)(2ax,2ay)(2ax,2ay)或(2axx,2ayy)(2axx,2ayy)(2axx,2ayy)。第二段同理。
{2ax2by2cy2dx1\left\{\begin{matrix} 2ax2by \\ 2cy2dx1 \end{matrix}\right.{2ax2by2cy2dx1
{2axx2by2cyy2dx1\left\{\begin{matrix} 2axx2by \\ 2cyy2dx1 \end{matrix}\right.{2axx2by2cyy2dx1
{2ax2byy2cy2dxx1\left\{\begin{matrix} 2ax2byy \\ 2cy2dxx1 \end{matrix}\right.{2ax2byy2cy2dxx1
{2axx2byy2cyy2dxx1\left\{\begin{matrix} 2axx2byy \\ 2cyy2dxx1 \end{matrix}\right.{2axx2byy2cyy2dxx1
第一个我们有2(ax−by)02(ax-by)02(ax−by)0且2(cy−dx)12(cy-dx)12(cy−dx)1。因为x,yx,yx,y互质显然(ax−by)(ax-by)(ax−by)和(cy−dx)(cy-dx)(cy−dx)都可以表示成任意整数。所有就有2k02k02k0且2k12k12k1显然无解。
同理第二个可以推出2kx02kx02kx0且2ky12ky12ky1就是xxx是偶数yyy是奇数
第三个推出2k−y02k-y02k−y0且2k−x12k-x12k−x1就是xxx是奇数yyy是偶数
第四个是2kx−y02kx-y02kx−y0且2ky−x12ky-x12ky−x1显然无解
也就是如果xyxyxy是奇数且gcd(x,y)1gcd(x,y)1gcd(x,y)1那么有p(x,y)1p(x,y)1p(x,y)1直接可以计算答案时间复杂度O(n2)O(n^2)O(n2)
定义w(x)w(x)w(x)表示1∼x1\sim x1∼x中与它互质且不是同奇偶的数的个数。若xxx是一个偶数那么显然没有偶数和它互质那么有w(x)φ(x)w(x)\varphi(x)w(x)φ(x)若xxx是奇数那么对于每个偶数yyy和它互质也一定有一个对应的奇数x−yx-yx−y和它互质那么有w(x)φ(x)2w(x)\frac{\varphi(x)}{2}w(x)2φ(x)。然后求和可以计算答案时间复杂度O(n)O(n)O(n)
考虑如何用杜教筛优化我们可以将问题转换为分开求奇数和偶数的φ\varphiφ和对于每个偶数一定可以被表示为2k(k≤n2)2k(k\leq \frac{n}{2})2k(k≤2n)那么如何kkk是偶数就有φ(2k)φ(k)\varphi(2k)\varphi(k)φ(2k)φ(k)如果kkk是奇数就有φ(2k)2∗φ(k)\varphi(2k)2*\varphi(k)φ(2k)2∗φ(k)也就是如果求出1∼n21\sim \frac{n}{2}1∼2n的奇偶的φ\varphiφ和就可以求出偶数的φ\varphiφ和然后杜教筛减去求出奇数的这是一个分治的过程可以通过本题。
时间复杂度O(n23logn)O(n^{\frac{2}{3}}\log n)O(n32logn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includemap
#define ll unsigned long long
using namespace std;
const ll N1e71;
ll T,n,cnt,mu[N],phi[N],pri[N];
ll sp1[N],sp2[N],p1[1100],p2[1100];
bool vis[N];
mapll,ll sp,sm;
void prime(){phi[1]1;for(ll i2;iN;i){if(!vis[i])pri[cnt]i,phi[i]i-1;for(ll j1;jcntpri[j]*iN;j){vis[pri[j]*i]1;if(i%pri[j]0){phi[i*pri[j]]phi[i]*pri[j];break;}phi[i*pri[j]]phi[pri[j]]*phi[i];}}for(ll i1;iN;i){sp1[i]sp1[i-1]phi[i]*(i1);sp2[i]sp2[i-1]phi[i]*(!(i1));}return;
}
ll GetSphi(ll n){if(nN)return sp1[n]sp2[n];if(sp[n])return sp[n];ll rest(n%2ull0ull)?((ll)n/2ull*(n1ull)):((ll)(n1ull)/2ull*n);for(ll l2ull,r;ln;lr1ull)rn/(n/l),rest-(r-l1ull)*GetSphi(n/l);return (sp[n]rest);
}
void dfs(ll x,ll n){p1[x]p2[x]0;if(nN){p1[x]sp1[n];p2[x]sp2[n];return;}dfs(x1,n/2);p2[x]p1[x1]p2[x1]*2ull; p1[x]GetSphi(n)-p2[x];return;
}
int main()
{prime();scanf(%llu,T);while(T--){scanf(%llu,n);dfs(0,n);printf(%llu\n,p1[0]p2[0]*2ull-1ull);}
}
