Problem 1

给定整数N,求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对.

就是求 \(\sum_{i=1}^{n} \sum_{j=1}^{n}[gcd(i,j)==P] \)

转化为 \(\sum_{p \in isprm}^{n} \sum_{i=1}^{\lfloor \frac {n}{p} \rfloor} \sum_{j=1}^{\lfloor \frac {n}{p} \rfloor }[gcd(i,j)==1] \)

实际上是求互质的数!

Ans= \(\sum_{p \in isprm}^{n}(\sum_{i=1}^{\lfloor \frac {n}{p} \rfloor}phi(i))*2-1 \)

 

 

Problem 2

[SDOI2008]仪仗队

似乎上一道题就解决了

 

Problem 3

[NOI2010]能量采集 求 \(\sum_{i=1}^{n} \sum_{j=1}^{m}  gcd(i,j) \)

实际上是求一个\(Ans= \sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)*2-1 \)

令\(f(d)=\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)==d] \)

所以 \(f(d)= \lfloor \frac{n}{d} \rfloor  *  \lfloor  \frac{m}{d}  \rfloor  –  \sum_{i=2}^{i *d <= n }  f ( i *d)  \)

则\(Ans=\sum_{i=1}^{n} f(i) ( (i-1)*2+1) \)

相当于枚举了GCD的结果,逆序做即可

 

分类: 数学题解

2
说点什么

avatar
2 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
maoxianguihawa130 Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
hawa130
游客

公式炸了…

maoxiangui
游客
maoxiangui

默默膜