[蓝桥杯 2018 国 B] 矩阵求和-Toy模板网

这篇具有很好参考价值的文章主要介绍了[蓝桥杯 2018 国 B] 矩阵求和。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

经过重重笔试面试的考验，小明成功进入 Macrohard 公司工作。

今天小明的任务是填满这么一张表：

表有 n 行 n 列，行和列的编号都从 1 算起。

其中第 ii 行第 jj 个元素的值是 gcd(i,j) 的平方，gcd 表示最大公约数，以下是这个表的前四行的前四列：
1  1  1  1
1  4  1  4
1  1  9  1
1  4  1 16
小明突然冒出一个奇怪的想法，他想知道这张表中所有元素的和。由于表过于庞大，他希望借助计算机的力量。

输入格式

一行一个正整数 n 意义见题。

输出格式

一行一个数，表示所有元素的和。由于答案比较大，请输出模1000000007（即109+7）后的结果。

输入输出样例

输入 #1复制
4
输出 #1复制
48
说明/提示

对于 30\%30% 的数据，n\le 1000n≤1000。

存在 10\%10% 的数据，n = 10^5n=105。

对于 60\%60% 的数据，n\le 10^6n≤106。

对于 100\%100% 的数据，n\le 10^7n≤107。

解题思路：要求∑∑gcd(i,j)²，

枚举最大公约数d,∑d∑∑(gcd(i,j)²==d)

把d替换成d²，∑d²∑∑(gcd(i,j)==d)

又(i/gcd(i,j))*(j/gcd(i,j))=1，上式化为 [蓝桥杯 2018 国 B] 矩阵求和

第三个求和可以用欧拉函数表示，即 [蓝桥杯 2018 国 B] 矩阵求和

接下来线性筛法求欧拉函数然后前缀和即可。文章来源地址https://www.toymoban.com/news/detail-477746.html

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int N=1e7+5;
int presum[N];
vector<int>prime;
bool vis[N];
int phi[N];
void get_phi(int n)
{
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])
        {
            phi[i]=i-1;
            prime.emplace_back(i);
        }
        for(int j=0;j<prime.size()&&i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];break;
            }
            else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}
int main( )
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    int mod=1e9+7;
    get_phi(n);
    for(int i=1;i<=n;i++)
    {
        presum[i]=presum[i-1]+phi[i];presum[i]%=mod;
    }
    ll ans=0;
    for(ll i=1;i<=n;i++)
    {
        ans=(ans+((i*i%mod)*(presum[n/i]*2-1))%mod)%mod;
    }
    cout<<ans;
    return 0;
}

到了这里，关于[蓝桥杯 2018 国 B] 矩阵求和的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！