Codeforces Round 904 (Div. 2)

Counting Rhyme

算法本质

思维

题目大意

给定n个数字，定义美丽数字对a b：

• 若x满足a%x==0 && b%x==0则x必然不等同于n个数字的某个

计数美丽数字对。

n <= 1e6
元素 <= n

思路推演

显然，其实就是gcd(a,b)不能被任意一个存在的数字整除，比如设其为g
这里每次运算其实存在3个元素：a b g，我们希望找到gcd(a,b) % g等于0或者不等于0的情况。

显然，从a入手是不可行的，题目讲元素大小限制在n，这些行为都在告诉我们，要从g入手。

从g入手也面临一些问题，其中最大的问题是重复。
观察某个例子：

4
2 3 12 4

这个例子中，需要考虑g为2 3 4的情况。

笔者在赛时对于重复的做法，采取容斥解决（因为其复杂度不会特别高），赛时没写完，赛后发现会T

这里实际是巧妙利用了调和级数的复杂度，g也是处于这个限制内的，这点是容易思考错过的。

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
int f(vector<int> &cnt, vector<int> &dp, int idx)
{
    if (dp[idx]!=-1)    return dp[idx];
    int num=0;
    for (int i=idx; i<=n; i+=idx)
        num += cnt[i];
    int res = num*(num-1)/2;
    for (int i=idx*2; i<=n; i+=idx)
        res -= f(cnt, dp, i);
    return dp[idx] = res;
}
inline void solve()
{
    cin>>n;
    // cnt[x]=y：值为x的元素个数是y
    // dp[x]=y：有x对元素的gcd值是y
    // vis[x]=1：元素对的gcd值为x时是不合法的，反之是合法的
    vector<int> cnt(n+5), dp(n+5, -1), vis(n+5);
    for (int i=1; i<=n; i++)
        cnt[in()]++;
    f(cnt, dp, 1);        // 记忆化搜索处理dp[]
    int ans=n*(n-1)/2;
    for (int val=1; val<=n; val++)
    {
        if (cnt[val]>0)    
            for (int w=val; w<=n; w+=val)
                vis[w] = 1;
        ans -= dp[val] * vis[val];
    }
    cout<<ans<<endl;
    return;
}

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。