2293 問題 U: 藍橋杯2018年第九屆真題-矩陣求和
時間限制: 1s
內(nèi)存限制: 128MB 提交: 704 解決: 48
題目描述
經(jīng)過重重筆試面試的考驗，小明成功進入 Macrohard 公司工作。
今天小明的任務(wù)是填滿這么一張表：
表有 n 行 n 列，行和列的編號都從1算起。
其中第 i 行第 j 個元素的值是 gcd(i, j)的平方，
gcd 表示最大公約數(shù)，以下是這個表的前四行的前四列：
1 1 1 1
1 4 1 4
1 1 9 1
1 4 1 16
小明突然冒出一個奇怪的想法，他想知道這張表中所有元素的和。
由于表過于龐大，他希望借助計算機的力量。
輸入
一行一個正整數(shù) n 意義見題。
對于 30% 的數(shù)據(jù)，n <= 1000
存在 10% 的數(shù)據(jù)，n = 10^5
對于 60% 的數(shù)據(jù)，n <= 10^6
對于 100% 的數(shù)據(jù)，n <= 10^7
輸出
一行一個數(shù)，表示所有元素的和。由于答案比較大，請輸出模 (10^9 + 7)(即：十億零七) 后的結(jié)果。
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點擊這里了解課程詳情