題意：求解小於n的數i且gcd（i，n）大於m的i的個數
分析：
對於所有小於n的最大公約數值一定是n的因子，所以，從這個方面下手找i為n的因子且i>m時求解車i的素數倍數且小於n的個數累加起來就好了。以為這個倍數最大為n/i所以求得n/i的歐拉函數值累加起來就好了。
代碼如下：
#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; long long euler(long long n){ //返回euler(n) long long res=n,a=n; for(long long i=2;i*i<=a;i++){ if(a%i==0){ res=res/i*(i-1);//先進行除法是為了防止中間數據的溢出 while(a%i==0) a/=i; } } if(a>1) res=res/a*(a-1); return res; } //歐拉函數值 long long a[1000010]; int main(){ long long n,m; int t; cin>>t; while(t--){ long long ans=0; scanf("%I64d%I64d",&n,&m); for(int i=1;i*i<=n;i++){//判斷sqrt（n)就好 if(n%i!=0)continue; if(i>=m&&i*i!=n){ ans+=euler(n/i); } if(n/i>=m){ ans+=euler(i);//一個是i，一個是n/i
} } printf("%I64d\n",ans); } return 0; }
C++編程新思維中的技巧，編程新思維技巧 1.編譯
c++加法高精度算法，加法高精度算法c++高精度算法，對於新
素數篩(1) 埃氏篩法，素數其原理就是先將2-n之內的所有數
SDUT OJ refresh的停車場 #includ
首先我們讓數組的元素都是由兩個數據域組成，data和c
