給定a,b,設G=gcd(a,b),于是有a=A*G,b=B*G(1<=A,B,gcd(A,B)=1)
對于a的多次加可以看成K*a(1<=k),轉化成(K*a)%b的所有結果能否表示成0..b-1中的所有數,
假(K*a)%b=M,M=K*a-W*b(W為使M>0的最大整數),M=K*A*G-W*B*G M%G==0,
既結果是G的倍數,如果想取得0..b-1中的所有數，
那么必須G=1才可能..
這算法牛X。。。

媽的，沒見過那么惡心的題目。。。
首先題目就錯了，1不是質數啊！！！
輸出之間居然還有一空行。。。
檢查了半天都沒查出來，殺人了！！！

懶得改了，用了同學的

傳說中的動態規劃。。。
注意題目的優先計算順序。先是考慮是否會小于0，然后才考慮是否會大于20，要不然就會WA。
哇塞,真的這樣,這題太假了。。。

Trie樹就是字典樹，其核心思想就是空間換時間。

舉個簡單的例子。

給你100000個長度不超過10的單詞。對于每一個單詞，我們要判斷他出沒出現過，如果出現了，第一次出現第幾個位置。
這題當然可以用hash來，但是我要介紹的是trie樹。在某些方面它的用途更大。比如說對于某一個單詞，我要詢問它的前綴是否出現過。這樣hash就不好搞了，而用trie還是很簡單。
現在回到例子中，如果我們用最傻的方法，對于每一個單詞，我們都要去查找它前面的單詞中是否有它。那么這個算法的復雜度就是O(n^2)。顯然對于100000的范圍難以接受。現在我們換個思路想。假設我要查詢的單詞是abcd，那么在他前面的單詞中，以b，c，d，f之類開頭的我顯然不必考慮。而只要找以a開頭的中是否存在abcd就可以了。同樣的，在以a開頭中的單詞中，我們只要考慮以b作為第二個字母的……這樣一個樹的模型就漸漸清晰了……
假設有b，abc，abd，bcd，abcd，efg，hii這6個單詞，我們構建的樹就是這樣的。

對于每一個節點，從根遍歷到他的過程就是一個單詞，如果這個節點被標記為紅色，就表示這個單詞存在，否則不存在。
那么，對于一個單詞，我只要順著他從跟走到對應的節點，再看這個節點是否被標記為紅色就可以知道它是否出現過了。把這個節點標記為紅色，就相當于插入了這個單詞。
這樣一來我們詢問和插入可以一起完成，所用時間僅僅為單詞長度，在這一個樣例，便是10。
我們可以看到，trie樹每一層的節點數是26^i級別的。所以為了節省空間。我們用動態鏈表，或者用數組來模擬動態。空間的花費，不會超過單詞數×單詞長度。

 

給出一個用類封裝的字典樹代碼，厄。。。做ACM的模板用另一個。。應該放在了“ACM模板”文件夾下了。。。

PS:實現方法http://met.fzu.edu.cn/eduonline/web/web/resources/articleContent.asp?id=346

     摘要: 今天總算是碰到一道復雜題了。。。（我BT了？）弄死我了，主要是排除重復情況，我想不通，最后參考了前人的代碼，修改后AC了。。。思路：通過遞歸，得出可能存在的解法，并記錄，查找原記錄，若存在相同則取消記錄 #include <iostream>#include <vector>#include <string>#include&nb...  閱讀全文

剛看了qsort的實現，正好碰到一道水題，試試哈。。。AC通過

<本文中排序都是采用的從小到大排序>
一、對int類型數組排序
程序代碼 程序代碼
int num[100];
Sample:
int cmp ( const void *a , const void *b )
{
     return *(int *)a - *(int *)b;
}
qsort(num,100,sizeof(num[0]),cmp);

二、對char類型數組排序（同int類型）
程序代碼 程序代碼
char word[100];
Sample:
int cmp( const void *a , const void *b )
{
    return *(char *)a - *(char*)b;
}
qsort(word,100,sizeof(word[0]),cmp)

三、對double類型數組排序（特別要注意）
程序代碼 程序代碼
double in[100];
int cmp( const void *a , const void *b )
{
    return *(double *)a > *(double *)b ? 1 : -1;
} qsort(in,100,sizeof(in[0]),cmp)；
 
四、對結構體一級排序
程序代碼 程序代碼
struct In {
 double data;
 int other;
}s[100]
//按照data的值從小到大將結構體排序,關于結構體內的排序關鍵數據data的類型可以很多種，
參考上面的例子寫
int cmp( const void *a ,const void *b)
{
     return (*(In *)a).data > (*(In *)b).data ? 1 : -1;
}
qsort(s,100,sizeof(s[0]),cmp);

五、對結構體二級排序
程序代碼 程序代碼
struct In {
   int x; int y;
}s[100];
//按照x從小到大排序，當x相等時按照y從大到小排序
int cmp( const void *a , const void *b )
{
    struct In *c = (In *)a;
    struct In *d = (In *)b;
    if(c->x != d->x) return c->x - d->x;
    else return d->y - c->y;
}
qsort(s,100,sizeof(s[0]),cmp);

六、對字符串進行排序
程序代碼 程序代碼
struct In {
   int data; char str[100];
}s[100];
//按照結構體中字符串str的字典順序排序
int cmp ( const void *a , const void *b )
{
    return strcmp( (*(In *)a)->str , (*(In *)b)->str );
}
qsort(s,100,sizeof(s[0]),cmp);

七、計算幾何中求凸包的cmp
程序代碼 程序代碼
int cmp(const void *a,const void *b)
//重點cmp函數，把除了1點外的所有點，旋轉角度排序
{
    struct point *c=(point *)a;
    struct point *d=(point *)b;
    if( calc(*c,*d,p[1]) < 0) return 1;
    else if( !calc(*c,*d,p[1])
   && dis(c->x,c->y,p[1].x,p[1].y) < dis(d->x,d->y,p[1].x,p[1].y))
   //如果在一條直線上，則把遠的放在前面
   return 1; else return -1;
}
 
PS: 其中的qsort函數包含在<stdlib.h>的頭文件里，strcmp包含在<string.h>的頭文件里

聽著Jay的《一路向北》，我一路水過來。。。今天真是啥水題都撞上了。。。

奇怪了，今天盡做些水題。。。啥也不說了，注意下1就行了，不算本身，和是0.。。

很賤的一道題。。。我本來以為可以隨便水的。。。結果還是WA了幾次
輸入的數居然可能是N千位。。。所以只能以字符串輸入了

后面還看到個小技巧，如2位數ab，a+b=a*10+b-9*10=ab%9