資工趴趴熊的小天地

Content

約瑟夫很喜歡參加程式比賽。他最喜歡的題目理所當然就是約瑟夫問題。

題目敘述如下:

有n個人編號從0到n-1圍成一圈。從第0個人數到第k個人將會被處決。

在那之後剩下來的人中編號為第k個人會接著被處決，一直到只剩下一個人為止。

這個人變是存活下來的唯一一個人。在這個問題裡將會給定n跟k並求最後生還者一開始的編號。

 

聰明如你當然知道這個問題的解法。解法相當的短，事實上只需要一個迴圈便可求得。

 r := 0; 

     for i from 1 to n do 

         r := (r + k) mod i; 

     return r;

其中 x mod y 表示x除以y後的餘數。

 

但約瑟夫不是相當的聰明。他懂得這個演算法，卻不懂背後的原理。因此他是實上只記得演算法的一部分，

而誤解了其中的一部分，且告訴他的朋友安卓這著名的問題解法如下:

     r := 0; 

     for i from 1 to n do 

         r := r + (k mod i); 

     return r;

 

安卓當場指證出了約瑟夫的錯誤，但卻也計算出了約瑟夫提供的演算法的錯誤答案結果，作為對照。

給你n和k請找出 

   ^{(k mod i) .}

5 3

7

解題參考:

https://home.gamer.com.tw/creationDetail.php?sn=4847431

python:

這個版本可以實現，但在zero judge 跟dome judge都會超時

while True:
    try:
        n,k=map(int,input().split())
        """
        k/i=q%r    144/49=2%46
        k/q=t      144/2=72%0   (72為最大值)
        (144/49 到144/72這段商都是2)
        """
        i=t=1  #因為題目是要%到1，所以可以反向從1開始
        sum = 0
        while(i <= k and i != n+1):
            q = k // i
            t = k // q  
            if(t>n):t=n #這一段等下做檢查    
            r=k%i
            sum+=( ( (r*2) - (t-i)*q)*(t-i+1)//2 ) #[2r + ( m - 1)*q ] * m / 2
            i=t+1
        if(i<=n):sum+=( (n-i+1)*k  )
        print(sum)
    except:
        break

C++版本一:(zero judge 會過但dome judge會超時)

#include <iostream>
using namespace std;
int main() {
	ios_base::sync_with_stdio(0);  
	cin.tie(0);  
	cout.tie(0);
	int n, k, i, t, q;
	long long sum;
	while (cin >> n >> k) {
		i = t = 1, sum = 0;
		while (i <= k && i != n + 1) {
			q = k / i, t = k / q;
			if (t > n)
				t = n;
			sum += ((long long)(k % i *2) - q * (t - i)) * (t - i + 1) /2;
			i = t + 1;
		}
		if (i <= n) 
			sum += (long long)(n - i + 1) * k;
		cout << sum << '\n';
	}
}

C++版本一:(zero judge 會過但dome judge會超時)

#include<iostream>
using namespace std;

int main(){
	long long n,k;
	while(cin>>n>>k){
		long long count = 0,i=1;
		while((i<k)&&(i<=n)){
			long long a,b; 
			a=k/i;
			b=k/a;
			if(i==b){
				count+=k%i;
			}
			else{
				if(b>n){
					count+=(k%i+k%n)*(n-i+1)/2;
					i=n; 
				}
				else{
					count+=(k%i+k%b)*(b-i+1)/2;
					i=b; 
				}		
			}
			i+=1;
		} 
		if(n>k){
			count+=k*(n-k); 
		}
		cout<<count<<endl;
	}
}