题解 P6860 【象棋与马】

QuantAsk · 2020-10-20 07:22:53 · 题解

出题人先来报个到，比赛的时候发现许多选手的做法都和我的不一样/kk。也有莫比乌斯反演过了的神仙。也十分感谢本题的验题人 beginend 和 my_dog。

T4 象棋与马

这个马能走到全图的充要条件显然是它能走到 (0,1)。考虑给出 x,y 求它能否走到 (0,1)。

算法1：

暴力 bfs 看是否能到达 (0,1) 或打表。

期望得分 5pts。

算法2：

请注意下文中 (X,Y) 表示当前马的坐标，x,y 表示马一步走的矩形的长和宽。

考虑从数论角度考虑本题。

首先如果当 gcd(x,y)\neq 1 显然不行。

因为走的顺序时无所谓的，所以可以将走的路程分成两段，一段只有是 (X\pm x,Y\pm y) 的位移，一段是只有 (X\pm y,Y\pm x) 的位移。

显然对于第一段能走到的点可以表示为 (2ax,2cy) 或 (2ax+x,2cy+y)。第二段同理为 (2by,2dx) 或 (2by+y,2dx+x)。其中 a,b,c,d\in \mathbb{Z}。那么我们可以推出公式有

设 k 是任意整数。

解第一个方程组得到 2(ax-by)=0 且 2(cy-dx)=1。因为 x,y 互质，所以 (ax-by) 和 (cy-dx) 都可以表示成任意整数。所有就有 2k=0 且 2k=1，显然无解。

同理第二个方程组可以推出 2k+x=0 且 2k+y=1，就是 x 是偶数，y 是奇数。

第三个方程组推出 2k-y=0 且 2k-x=1，就是 x 是奇数，y 是偶数。

第四个方程组推出 2k+x-y=0 且 2k+y-x=1，显然无解。

所以 p(x,y)=1 当且仅当 gcd(x,y)=1 且 x+y 是一个奇数。

然后暴力求出所有的 p(x,y) 即可，期望得分 20pts。

算法3：

如果 x+y 是一个奇数那么 x-y 也是一个奇数，所以 gcd(x,x-y)=1 且 x-y 是一个奇数也是 p(x,y)=1 的充要条件。

定义 w(x) 表示 1\sim x 中有多少个奇数与 x 互质，考虑如何计算 w(x)。

显然如果 x 是一个偶数，那么没有偶数与它互质，即 w(x)=\varphi(x)，我们不难发现 ans=\sum_{i=1}^{n}w(x)\times 2-2。

如果 x 是一个奇数，对于一个奇数 k，有 gcd(x,k)=1 那么就有 gcd(x,x-k)=1 也就是对于每个奇数与它互质那么一定有一个对应的偶数 x-k 与它互质，也就是 w(x)=\frac{\varphi(x)}{2}，当然对于 w(1) 需要进行特判。

那么显然线性求 \varphi 就可以获得 50pts。

算法4：

显然答案就是奇数的 \varphi 加上偶数的 \varphi 除以 2。所以我们需要分开计算奇数和偶数的 \varphi

若 n 是一个偶数，假设我们已经求出了 p1=\sum_{i=1}^{n\div2}\varphi(x) （x 是奇数）和 p2=\sum_{i=1}^{n\div 2}\varphi(x)（x 是偶数）那么考虑如何求到 n。首先我们有 \sum_{i=1}^n\varphi(x) （x 是偶数）=p1+p2\times 2。（对于每个奇数乘上一个 2，根据 \varphi 的定义我们发现它多了一个 2 这个因子，而 n 乘上了一个 2，所以 \varphi 不变；而对于一个偶数乘上了一个 2，没有加减因子，但是 n 乘上了一个 2，所以它的 \varphi 也要乘 2）。

然后用杜教筛求出 \sum_{i=1}^n \varphi(x) 然后减去前面求出的答案就是奇数的答案了。时间复杂度 O(n^{\frac{2}{3}}\log n)，预处理到 1\sim 10^7 的答案即可大大缩小时间复杂度。

期望得分100pts。

算法5:

其实最终式子可以优化为递推式

看到最终许多通过的选手都是写成这种形式的

others

对于65的部分分是给莫比乌斯反演的，没想到有人能优化到可以通过的形式。对于ull自然溢出需要注意的地方，就是在杜教筛中 n\times (n+1) 时需要注意让偶数的那个先除以2否则会溢出之后再除上一个 2 就会出现 Wrong\ Answer 的情况。

然后还有人写到 35 的部分分是我没有预料到的（因为我都不会写，果然选手的智慧是无限的）。

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define ll unsigned long long
using namespace std;
const ll N=1e7+1;
ll T,n,cnt,mu[N],phi[N],pri[N];
ll sp1[N],sp2[N],p1[1100],p2[1100];
bool vis[N];
map<ll,ll> sp,sm; 
void prime(){
    phi[1]=1;
    for(ll i=2;i<N;i++){
        if(!vis[i])pri[++cnt]=i,phi[i]=i-1;
        for(ll j=1;j<=cnt&&pri[j]*i<N;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 i=1;i<N;i++){
        sp1[i]=sp1[i-1]+phi[i]*(i&1);
        sp2[i]=sp2[i-1]+phi[i]*(!(i&1));
    }
    return;
}
ll GetSphi(ll n){
    if(n<N)return sp1[n]+sp2[n];
    if(sp[n])return sp[n];
    ll rest=(n%2ull==0ull)?((ll)n/2ull*(n+1ull)):((ll)(n+1ull)/2ull*n);
    for(ll l=2ull,r;l<=n;l=r+1ull)
        r=n/(n/l),rest-=(r-l+1ull)*GetSphi(n/l);
    return (sp[n]=rest);
}
void dfs(ll x,ll n){
    p1[x]=p2[x]=0;
    if(n<N){
        p1[x]=sp1[n];
        p2[x]=sp2[n];
        return;
    }
    dfs(x+1,n/2);
    p2[x]+=p1[x+1]+p2[x+1]*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);
    }
}