ZYCode ICPC Round 7 吃饭

nfls_old_salty_fish · 2023-12-01 18:32:44 · 个人记录

O(n^3) 解法

对于每个 n,m , 暴力模拟

O(n^2) 解法

对于每组 n,m , 我们抽象成这样的问题：一开始 x=0 ，每次操作 x=x+m , 在多少次操作后, x \equiv 0 (\mod n)。\ 显然， x 最后的值等于 \frac {n \times m}{\gcd(n,m)}，就是两数的最小公倍数，那么显然，他操作了 \frac{n}{\gcd(n,m)} 次，就是一圈可以坐这么多人，然后回到一个做过人的点。\ 显然，当这个数是偶数时，这组 n,m 是合法的。

O(n) 解法

考虑 \frac{n}{\gcd(n,m)} 的奇偶性，仅当 m 中质因子 2 的数量大于等于 n 中质因子 2 的数量时，这组 n,m 非法。\ 设 n 的 2 质因子之积为 p, 则 m 不应该是 p 的倍数。

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
int n,ans; 
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int cnt=1,t=i*2;
        while(t%2==0)cnt*=2,t/=2;
        ans+=i-i/cnt;
        ans%=1226999999;
    }
    cout<<ans;
    return 0;
}

O(\log n) 做法

注意到 p 只能是 2 的次方，枚举 p 即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1226999999;
int n,ans;
int last(int i){
    int t=n/i*i;
    if(t/i%2==0)t-=i;
    return t;
}
int sum(int st,int ed,int gc){
    if((st+ed)%2==0)return (st+ed)/2%mod*(((ed-st)/gc+1)%mod)%mod;
    return ((ed-st)/gc+1)/2%mod*((st+ed)%mod)%mod;
}
signed main(){
//  freopen("10.in","r",stdin);
//  freopen("10.out","w",stdout); 
    cin>>n;
    for(int i=1;i<=n;i*=2){
        int end=last(i);
        ans+=sum(i,end,i*2)-sum(0,end/i/2,1);
        ans=(ans+mod)%mod;
    }
    cout<<ans;
    return 0;
}