Code 備忘錄►Math

STEP5::Problem 0012 : Ch2-1.言靈

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0012
這題求n個數字中任意數字加起來為m的倍數。

因為題目有說 N>=M，所以–N個數字中亂亂加一定會出現M的倍數。
所以只要求區間合等於M的倍數就好。
一開始輸入先MODm，等於0就輸出。
不等於零就加到sum裡，sum持續MODm，如果等於0就輸出1到i。
如果不等於，就在S[sum]中記錄i是多少，下一次如果sum又等於這次的sum(S[sum]不等於0)，就代表中間這段和等於0(m的倍數)，就輸出這段。
輸入優化因為有測資結尾不是 空白或換行，害我一開始TLE…..

2016/1/25

真看不懂我以前在寫甚麼鬼，題目有保證一定有解，跟N>=M沒有關係…。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <cstdio>
#include <cstdlib>
#include <iostream>
#define N 5000001
#define LL long long
using namespace std;
int S[N]={0};
inline int in()//輸入優化
{   
  char cha;   
  unsigned int x=0,flag=1;
  while(cha=getchar())   
  if(cha!=' '&&cha!='\n')break;
  if(cha!='-'){
       x=x*10+cha-'0';  
   }else{
         flag=-1; 
   }  
  while(cha=getchar())    
    {   
     if(cha<'0'||cha>'9')break;
      x=x*10+cha-48;   
    }   
    return x*flag;
}
int main(int argc,char *argv[])
{
    //while(int aa=in())printf("%d\n",aa);
    int n,m,a;
    //scanf("%d %d",&n,&m);
    n=in();m=in();
    LL sum=0,tmp=0;
    for(int i=1;i<=n;i++){
            //scanf("%d",&a);
            a=in();
            tmp=(a%m+m)%m;
            if(!tmp){printf("1\n%d\n",i);goto end;}
            sum=(sum+tmp)%m;
            //printf("DD:%d(%d)\n",i,sum);
            if(sum==0){
                printf("%d\n1",i);
                for(int j=2;j<=i;j++)
                        printf(" %d",j);
                puts("");
                goto end;
            }
            else if(S[sum]){
                //printf("%d(%d)\n",i-S[sum],i);
                printf("%d\n%d",i-S[sum],S[sum]+1);
                for(int j=S[sum]+2;j<=i;j++)
                        printf(" %d",j);
                puts("");
                goto end;
            }else
                S[sum]=i;
    }
    
    end:;//system("pause");
    return 0;
}