T3 題解

題目：

題目背景

• 致遠(yuǎn)星艦隊(duì)旗艦——“養(yǎng)生壺”號(hào)上（別問為啥，外星人的語言習(xí)慣）

• 裝著全致遠(yuǎn)星最先進(jìn)的密碼保護(hù)系統(tǒng)

• 你作為OI星最強(qiáng)的間諜——（代號(hào)：映山紅）

• 偷偷來到了這艘戰(zhàn)艦上

• 你經(jīng)歷重重歷險(xiǎn)終于來到了戰(zhàn)艦的總控室

• 密碼系統(tǒng)作為高級(jí)貨當(dāng)然不是靜態(tài)的

• 它描繪的是這樣一個(gè)問題：

• 計(jì)算滿足：1到n內(nèi)，gcd(x,y)為素?cái)?shù)的數(shù)對(duì)有多少。

• 現(xiàn)在帝國(guó)的護(hù)衛(wèi)隊(duì)已經(jīng)發(fā)現(xiàn)了你的蹤跡

• 你能夠使用的就是一臺(tái)性能與公元$2000$年電腦性能幾乎無差的掌上解碼器

• 你需要在盡可能短的時(shí)間內(nèi)算出問題的答案

題目描述

• 求1≤x,y≤n中 , 滿足：gcd(x,y)為素?cái)?shù)的數(shù)對(duì)有多少。

輸入格式

• 一行一個(gè)數(shù)n

輸出格式

• 一行一個(gè)數(shù) , 表示滿足條件的數(shù)對(duì)數(shù)量

輸入輸出樣例

輸入 #1

4

輸出 #1

4

輸入 #2

12

輸出 #2

39

說明/提示

• 對(duì)于10%的數(shù)據(jù)，保證n≤10

• 對(duì)于50%的數(shù)據(jù)，保證n≤10⁵

• 對(duì)于100% 的數(shù)據(jù) , 保證n≤10⁷

• 數(shù)據(jù)隨機(jī)生成 , 大佬們可以暴力踩標(biāo)程 (bushi)

翻譯一下題意：給定一個(gè)正整數(shù)n，求1≤x,y≤n中滿足gcd(x,y)為素?cái)?shù)的數(shù)對(duì)有多少。

思路：

既然gcd(x,y)是一個(gè)質(zhì)數(shù)，那么我們可以認(rèn)為，如果我們假設(shè)gcd(x,y)的值為p，則gcd(x/p,y/p)的值一定為1。既然這樣，那么我們就可以先求出1到n中所有的素?cái)?shù)，然后再依次求出對(duì)于1到n/p[i]的x和y，滿足gcd(x,y)=1的素?cái)?shù)的個(gè)數(shù)。

我們?cè)谇髮?duì)于每一對(duì)1≤x,y≤n/p[i]的x和y，滿足gcd(x,y)=1的數(shù)對(duì)的對(duì)數(shù)時(shí)，不妨設(shè)x≤y（如果不滿足則交換x和y的順序）。

我們考慮對(duì)于每一個(gè)確定的y，因?yàn)閤≤y，所以對(duì)于每一對(duì)1≤x,y≤n/p[i]的x和y，當(dāng)我們給定一個(gè)確定的y值的時(shí)候，滿足gcd(x,y)=1的數(shù)對(duì)的對(duì)數(shù)就等于φ(y)的值。

因而，對(duì)于每一對(duì)1≤x,y≤n/p[i]的x和y，滿足gcd(x,y)=1的數(shù)對(duì)的對(duì)數(shù)就等于∑(i=1->n/p[i])φ(i)。

這樣我們就可以得出這道題的完整思路：

我們先跑一遍篩素?cái)?shù)（這里用線性篩即可），篩出1到n之間的所有質(zhì)數(shù)，以及求出1到n之間每個(gè)數(shù)i的φ(i)的值，然后再枚舉質(zhì)數(shù)，求出對(duì)于1到n的每一個(gè)質(zhì)數(shù)p[i]，它所對(duì)應(yīng)的∑(i=1->n/p[i])φ(i)的值，最后再一次進(jìn)行累加求和。

完整代碼（by 巨佬HWH）：

 1 #include<cstdio>
 2 #define ll long long
 3 using namespace std;
 4 
 5 const ll N=1e7+9;
 6 ll pr[N],ph[N];
 7 
 8 int main()
 9 {
10     register ll n,i,j,k=0,p;
11     register long long s=0,t=0;
12     
13     scanf("%lld",&n);
14     
15     ph[1]=1;
16     for(i=2;i<=n;++i)
17     {    
18         if(!ph[i]) pr[++k]=i,ph[i]=i-1;
19         for(j=1;p=i*pr[j],p<=n&&j<=k;++j)
20         {
21             if(i%pr[j]==0)
22             {
23                 ph[p]=ph[i]*pr[j];
24                 break;
25             }
26             else ph[p]=ph[i]*ph[pr[j]];
27         }
28     }
29     
30     for(i=1,j=k;j;--j)
31     {
32         for(p=n/pr[j];i<=p;++i)t+=ph[i];
33         s+=t;
34     }
35     
36     printf("%lld",(s<<1)-k);
37     return 0;
38 }