反倍數
【問題描述】
給定三個整數 a, b, c，如果一個整數既不是 a 的整數倍也不是 b 的整數倍還不是 c 的整數倍，則這個數稱為反倍數，
請問在 1 至 n 中有多少個反倍數，
【輸入格式】
輸入的第一行包含一個整數 n，
第二行包含三個整數 a, b, c，相鄰兩個數之間用一個空格分隔，
【輸出格式】
輸出一行包含一個整數，表示答案，
【樣例輸入】
30
2 3 6
【樣例輸出】
10
【樣例說明】
以下這些數滿足要求：1, 5, 7, 11, 13, 17, 19, 23, 25, 29，
【評測用例規模與約定】
對于 40% 的評測用例，1 <= n <= 10000，
對于 80% 的評測用例，1 <= n <= 100000，
對于所有評測用例，1 <= n <= 1000000，1 <= a <= n，1 <= b <= n，1 <= c <= n，
題解：
#include<iostream>
#include<algorithm>
using namespace std;
int gys(int m,int n){
if(n>m) //函式求最大公約數
swap(m,n);
while(int r=m%n){
m=n;
n=r;
}
return n;
}
int main(){
int n,a[3],res=0;
cin>>n;
for(int i=0;i<3;i++)
cin>>a[i];
sort(a,a+3); //將a,b,c按從小到大排序
if(a[1]%a[0]==0){ //分不同情況進行討論
if(a[2]%a[0]==0) //b,c都是a的倍數
res=n-n/a[0];
else //b是a的倍數但c不是a的倍數
res=n-n/a[0]-n/a[2]+n/(a[0]*a[2]/gys(a[2],a[0]));
}
else{
if(a[2]%a[0]==0) //b不是a的倍數但c是a的倍數
res=n-n/a[0]-n/a[1]+n/(a[0]*a[1]/gys(a[1],a[0]));
else{
if(a[2]%a[1]==0) //b,c都不是a的倍數但b是c的倍數
res=n-n/a[0]-n/a[1]+n/(a[0]*a[1]/gys(a[1],a[0]));
else //b,c都不是a的倍數而且b也不是c的倍數
res=n-n/a[0]-n/a[1]-n/a[2]+n/(a[0]*a[1]/gys(a[1],a[0]))+n/(a[0]*a[2]/gys(a[2],a[0]))+n/(a[1]*a[2]/gys(a[2],a[1]))-n/(a[0]*a[1]*a[2]/gys(gys(a[2],a[1]),a[0]));
} //這種情況最為復雜
}
cout<<res<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/248209.html
標籤：其他
上一篇：作業統計程式4.0
下一篇：unity Camera相機組件 和 cinemachine攝像機組件 功能實作 鏡頭角度旋轉、平移、縮放、位置重置、自動避障、多攝像機切換等功能相關設定技巧