Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:跳蚤

Posted by ryangiggsy at 2007-08-01 20:58:47 on Problem 1091
In Reply To:跳蚤 Posted by:czfhhh at 2005-11-10 21:31:28
> 1.易证,可以完成任务的充要条件为n+1个数的最大公约数为1。
> 2.若m为质数,则除了n+1个m的情况外,都可完成任务,即有m^n-1种情况。
> 3.若m为合数,则可能的最大公约数必为m的质因数的倍数。可以算出所有最大公约数的质因数含p的情况有(m/p)^n种。
> 4.设m的质因数为a1,a2,...,aT。则最大公约数不为1的所有情况数为(1<=i1<=T)∑((m/ai1)^n)- (1<=i1<i2<=T)∑((m/(ai1*ai2))^n)+…-(-1)^(T-1)*(1<=i1<i2<…<i(T-1)<=T)∑((m/(ai1*ai2*…*ai(T-1)))^n)-(-1)^T* (1<=i1<i2<…<iT<=T)∑((m/(ai1*ai2*…*aiT))^n)。用m^n减去所有情况数即是可完成任务数。


你的公式没有完全看懂 但是似乎有一点容斥原理的感觉 不知道是不是?

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator