---

链接：

题意：万圣节到了，有 c 个小朋友向 n 个住户要糖果，根据以往的经验，第i个住户会给他们a[ i ]颗糖果，但是为了和谐起见，小朋友们决定要来的糖果要能平分，所以他们只会选择一部分住户索要糖果，这样糖果恰好可以平分又不会剩下，输出索要糖果的用户编号。如果没有任何一组住户给的糖果总数能够平分，则输出 "no sweets" 。SPJ（ 意味着答案不唯一 ）

思路：

• 简单鸽巢原理题目，可以将问题转化成

  给出一个正整数序列A1,A2, ... ,An ，求有没有整数 l 和 r ( 1<= l < r <= n ) ，使得 Al + .... + Ar 是 C的倍数。

• 题目已知 A[]，构造序列 Si = A1 + A2 + A3 + ... + Ai （ 1 <= i <= n ），则有两种可能
  1. Si % C == 0
  2. 任意的 Si 都不是C的倍数 ，令 Ri ≡ Si mod C ( 1<= i <= n )
     既然所有的Si都不是C的倍数，那 Ri 的取值范围应该在[ 1 , C-1 ] 之间，现在有 n 个Ri 分布到 C-1 个位置上并且 n >= C ，所以在区间 [ 1 , C-1 ] 之间一定至少会有两个 R 的值是相等的，设这两个相同 R 值的 S 分别为 Sh 和 Sk ( k > h )，则 ( Sk - Sh ) mod C == 0，即 Ak+1 , Ak+2 , ... ，Ah 这段序列的和为 C 的倍数

• 再来思考这道题，根据上面的分析，可以得知这道题是一定有解的...... 所以根本不需要输出一个 "no sweets"

---

<font color = blue , size = '4'>下面是做这道题的三个代码，很能体现出代码优化的重要性，希望以后在做完题之后能坚持优化自己的代码，不以A题为目的，共勉。

最后有福利 /滑稽

1.想用vector来存一下余数相同的 位置 i

/*************************************************************************    > File Name: poj3370.cpp    > Author:    WArobot     > Blog:      http://www.cnblogs.com/WArobot/     > Created Time: 2017年04月29日 星期六 15时06分01秒 ************************************************************************/#include
    
     #include
     
      using namespace std;#define maxn 100100int c,n;int a[maxn];long long S[maxn];vector
      
        Rem[maxn];  // 定义一个余数的链表int main(){    while(~scanf("%d%d",&c,&n) && (c||n)){        for(int i=0;i
       
        =2){                    ok = 1;                    for(int j=Rem[i][0]+1;j<=Rem[i][1];j++)                        printf("%d%c",j,j==Rem[i][1]?'\n':' ');                    break;                }            }            if(!ok) printf("no sweets\n");        }    }    return 0;}
       
      
     
    

2.用vis[]标记之前是否出现过余数，并且 S[ i ] = ( a[i] + S[i-1] ) 可以优化成S[ i ] = ( a[i] + S[i-1] )%c，使得数组S中只用来存放余数而不在存放 和，在计算余数的时候不会多次计算 S[i]%c 的值，缩减了一下时间。

/*************************************************************************    > File Name: poj3371t2.cpp    > Author:    WArobot     > Blog:      http://www.cnblogs.com/WArobot/     > Created Time: 2017年04月29日 星期六 16时12分38秒 ************************************************************************/#include
    
     #include
     
      #include
      
       using namespace std;const int maxn = 100010;int c,n;int a[maxn] , vis[maxn];long long sum[maxn];void print(int a,int b){    for(int i=a;i<=b;i++)           printf("%d%c",i,i==b?'\n':' ');    return;}int main(){    while(~scanf("%d%d",&c,&n) && (c+n)){        memset(vis,0,sizeof(vis));        for(int i=1;i<=n;i++)   scanf("%d",&a[i]);        sum[0] = 0;        for(int i=1;i<=n;i++){            sum[i] = a[i]+sum[i-1];            if(sum[i]%c==0){                print(1,i);                break;            }            if(vis[sum[i]%c]){                print(vis[sum[i]%c]+1,i);                break;            }            vis[sum[i]%c] = i;        }    }    return 0;}
      
     
    

3.后来发现数组 S[ ] 也是多浪费空间的，改成了一个整型 S，节省一下空间

/*************************************************************************    > File Name: poj3371t2.cpp    > Author:    WArobot     > Blog:      http://www.cnblogs.com/WArobot/     > Created Time: 2017年04月29日 星期六 16时12分38秒 ************************************************************************/#include
    
     #include
     
      using namespace std;const int maxn = 100010;int c,n;int a[maxn] , vis[maxn] , S;void print(int a,int b){    for(int i = a ; i < b ; i++)            printf("%d ", i);    printf("%d\n", b);}int main(){    while(~scanf("%d%d", &c, &n) && (c+n)){        memset(vis, 0, sizeof(vis));        for(int  i = 1; i <= n; i++)    scanf("%d",&a[i]);        S = 0;        for(int i = 1; i <= n; i++){            S = ( a[i] + S ) % c;            if ( S == 0 ){                print( 1 , i );         break;            }            if ( vis[ S ] ){                print( vis[ S ] + 1 , i );      break;            }            vis[ S ] = i;        }    }    return 0;}
     
    

---

福利来了，博主在杭电上也发现了一道一模一样的题（ HDU1808 ），并且还get到一个非常有趣的方法

#include
    
     using namespace std;int main(){    int c,n,x;    while(~scanf("%d%d",&c,&n) && c+n){        for(int i=0;i
    

对，你没有看错！ 竟然A了！！！ 可见这道题杭电上的数据没POJ强 2333 ，这样做也是没问题的，小朋友们一块糖也不要不就行了吗？哈哈 有趣的小朋友！