題目鏈接：傳送門
題意：求區間[a,b]內與n互質的數的個數。
思路：用容斥求出[1-b]與n互質的個數—[1-(a-1)]內與n互質的個數。
#include #include #include #include #include #include #include #include #include #include #include #include #include #define maxn 360 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 1000000007 #define pp pair #define ull unsigned long long #define max(x,y) ( ((x) > (y)) ? (x) : (y) ) #define min(x,y) ( ((x) > (y)) ? (y) : (x) ) using namespace std; _ll fac[maxn],tot,A,B,N,ans; void div(int x) { tot=0; for(_ll i=2;i*i<=x;i++) { if(x&&x%i==0) { fac[tot++]=i; while(x&&x%i==0)x/=i; } } if(x>1)fac[tot++]=x; } void dfs(_ll num,_ll s,_ll r,_ll n) { if(num==tot) { if(s&1)ans-=n/r; else ans+=n/r; return ; } dfs(num+1,s,r,n); dfs(num+1,s+1,r*fac[num],n); } int cas=1; void solve() { div(N); ans=0;dfs(0,0,1,B);_ll ans_1_b=ans; ans=0;dfs(0,0,1,A-1);_ll ans_1_a=ans; printf("Case #%d: %I64d\n",cas++,ans_1_b-ans_1_a); } int main() { int T; scanf("%d",&T); while(T--) { scanf("%I64d%I64d%I64d",&A,&B,&N); solve(); } return 0; }
ZOJ 3647 Gao the Grid（居然是暴力）
POJ 2299 Ultra-QuickSort £¨¹é²
NYOJ 1076 方案數量（公式 或 遞推） 方案數
上一篇：C++ Builder 初學問
string類型轉換int類型本文地址: http:/
線索化二叉樹 這是數據結構課程裡
