1005 今夕何夕

1001 小C的倍数问题

Accepts: 1990

Submissions: 4931

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Problem Description

根据小学数学的知识，我们知道一个正整数x是3的倍数的条件是x每一位加起来的和是3的倍数。反之，如果一个数每一位加起来是3的倍数，则这个数肯定是3的倍数。

现在给定进制P，求有多少个B满足P进制下，一个正整数是B的倍数的充分必要条件是每一位加起来的和是B的倍数。

Input

第一行一个正整数T表示数据组数(1<=T<=20)。

接下来T行，每行一个正整数P(2 < P < 1e9)，表示一组询问。

Output

对于每组数据输出一行，每一行一个数表示答案。

Sample Input

110

Sample Output

3 P-1的因子个数

#include 
     
       #include 
      
        #include 
       
         #include 
        
         #include 
         
           #include 
          
            #include 
           
             #include 
            
             #include 
             
              #include 
              
               #include 
               
                 #include 
                
               
              
             
            
           
          
         
        
       
      
     

 

1002 数据分割

Accepts: 102

Submissions: 1332

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Problem Description

小w来到百度之星的赛场上，准备开始实现一个程序自动分析系统。

这个程序接受一些形如xi=xjx_i = x_jx​i​​=x​j​​ 或 xi≠xjx_i \neq x_jx​i​​≠x​j​​ 的相等/不等约束条件作为输入，判定是否可以通过给每个 w 赋适当的值，来满足这些条件。

输入包含多组数据。 然而粗心的小w不幸地把每组数据之间的分隔符删掉了。 他只知道每组数据都是不可满足的，且若把每组数据的最后一个约束条件去掉，则该组数据是可满足的。

请帮助他恢复这些分隔符。

Input

第111行：一个数字LLL，表示后面输入的总行数。

之后LLL行，每行包含三个整数，i,j,ei,j,ei,j,e，描述一个相等/不等的约束条件，若e=1e=1e=1，则该约束条件为xi=xjx_i = x_jx​i​​=x​j​​ ，若e=0e=0e=0，则该约束条件为 xi≠xjx_i \neq x_jx​i​​≠x​j​​ 。

i,j,L≤100000 i,j,L \leq 100000i,j,L≤100000

xi,xj≤Lx_i , x_j \leq L x​i​​,x​j​​≤L

Output

输出共T+1T+1T+1行。

第一行一个整数TTT，表示数据组数。

接下来TTT行的第iii行，一个整数，表示第i组数据中的约束条件个数。

Sample Input

62 2 12 2 11 1 13 1 11 3 11 3 0

Sample Output

16 并查集，按条件加入集合中。满足条件时，加入集合，不满足时说明是该组最后一组数据，清空即可。

#include 
       
         #include 
        
          #include 
         
           #include 
          
           #include 
           
             #include 
            
              #include 
             
               #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                   #include 
                  

s[100005],v;set

::iterator it;int ans,f[100005],pos[100005];int L,x,y,fx,fy,cnt,w;int find(int x){ return f[x]==x?x:find(f[x]);}void uion(int x,int y){ if(x==y) return ; if(s[x].size()>s[y].size()) swap(x,y); for(it=s[x].begin();it!=s[x].end();it++)//因为有这种情况：x和y相等，x和z不相等，那么y和z肯定也不相等 //也就是说只要z和x不相等，那么和x在同一个并查集合里的所有数都和z不相等 { s[*it].erase(x); s[*it].insert(y); s[y].insert(*it); } f[x]=y;}int main(){ for(int i=0;i<=100005;i++) f[i]=i; scanf("%d",&L); cnt=0;ans=0;//Recoding the number of date per case//Recoding the numper of case; while(L--) { cnt++; scanf("%d%d%d",&x,&y,&w); v.insert(x);v.insert(y); fx=find(x);fy=find(y); if(w==1) { if(fx==fy || s[fx].count(fy)==0) uion(fx,fy);//can satisfy else { //not satisfy,delete; pos[++ans]=cnt; cnt=0;//Recoding the number of date per case; for(it=v.begin();it!=v.end();it++)//for the new Case,so clear completely { s[*it].clear(); f[*it]=*it; } v.clear(); } } else { if(fx==fy)//not satisfy,delete { pos[++ans]=cnt; cnt=0; for(it=v.begin();it!=v.end();it++)//for the new Case,so clear completely { s[*it].clear(); f[*it]=*it; } v.clear(); } else s[fx].insert(f[y]),s[fy].insert(fx);//can satisfy } } printf("%d\n",ans); for(int i=1;i<=ans;i++) printf("%d\n",pos[i]); return 0;}