本文共 727 字，大约阅读时间需要 2 分钟。

所有用到的数在$[L,R]$范围内的前提下

求出有多少$y$满足$gcd(y-k,y+k)$

看上去非常不好做,实际上可以转化一下

找$gcd(y,y+2k)==1$的数目

当然此时$L<=y<=R-2k$

就是求$gcd(y,2k)==1$的数量

似乎仍然不是很好求,但是,但是可以容斥!!!

分解$2k$的质因子,枚举相同的质因子是哪些,根据质因子奇偶个数来判断是加还是减

注意特判$R-2k<L$直接输出零

$L==0$时也需要判断,因为$L-1$是$-1$,会影响答案

#include 
   
    using namespace std;#define int long longint L,R,k,my[100],ans;void fz(int x){
   	for(int i=2;i*i<=k;i++)	{
   		if( x%i==0 )	my[++my[0]] = i;		while( x%i==0 )	x/=i;	}	if( x!=1 )	my[++my[0]] = x;}signed main(){
   	cin >> L >> R >> k;	k*=2; R-=k; fz(k);	if( R
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/112808849 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！