ural 1091

题目：http://acm.timus.ru/problem.aspx?space=1&num=1091

题意：从 s 个数里挑出 k 个, 这个 k 个数的共因子大于 1 一共有多少种方法

直接暴搜，注意剪枝优化

View Code

 1 typedef long long ll;
 2 const int N = 60;
 3 int ans,k,s;
 4 bool vis[N];
 5 int flag;
 6 int gcd(int a,int b)
 7 {
 8     if(!b) return a;
 9     else return gcd(b,a % b);
10 }
11 bool juge()
12 {
13     int i;
14     for(i = 0; i <= s; i++)
15     if(vis[i]) break;
16     int g = i;
17     while(i <= s)
18     {
19         if(vis[i])
20         {
21             g = gcd(max(g,i),min(g,i));
22             if(g == 1) return false;
23         }
24         i ++;
25     }
26     return true;
27 }
28 void dfs(int x,int num)
29 {
30     if(x > s + 1 || k + x - num > s + 1 || !juge()) return ;
31     if(num == k)
32     {
33         if(juge()) ans ++;
34         if(ans > 10000)
35         {
36             flag = 1, ans = 10000; //return ;
37         }
38         return ;
39     }
40     vis[x] = true;
41     dfs(x + 1,num + 1);
42     vis[x] = false;
43     dfs(x + 1,num);
44 }
45 int main()
46 {
47     int i,j;
48     while(scanf("%d%d",&k,&s) != EOF)
49     {
50         ans = 0;
51         flag = 0;
52         dfs(2,0);
53         printf("%d\n",ans);
54     }
55     return 0;
56 }

题目：http://acm.timus.ru/problem.aspx?space=1&num=1204

题意：给出同余式，然后找出所有在 n 以内的数x ，使得满足给的关系式

根据同余的性质：a 和 b 同余 n ，那么 a 和 b 的差就是 n 的倍数。所以题目的方程式就可以转换为：x * (x - 1) % n == 0，因为题目说了 n == p1 * p2（p1 p2 是两个不同的素数，假设p1 < p2），所以对 n 分解，然后从p2 开始枚举 1 * p2 , 2 * p2, 3 * p2 ~~~~p1 * p2

View Code

 1 const int N = 31630;
 2 int prime[N];
 3 bool vis[N];
 4 int num;
 5 void is_prime()
 6 {
 7     int i,j;
 8     for(i = 2; i < N ;i++)
 9     {
10         if(!vis[i])
11         {
12             prime[num ++] = i;
13             for(j = 1; j * i < N; j++)
14             {
15                 if(vis[i * j]) continue;
16                 vis[i * j] = true;
17             }
18         }
19     }
20 }
21 int main()
22 {
23     num = 0;
24     is_prime();
25     int n,t,i;
26     scanf("%d",&t);
27     while(t--)
28     {
29         scanf("%d",&n);
30         //cout<<prime[n - 1]<<endl;
31         for(i = 0; i < num; i++)
32         if(n % prime[i] == 0) break;
33         int p = prime[i], q = n / prime[i];
34         //cout<<"p = "<<p<<" "<<q<<endl;
35         printf("0 1");
36         for(i = q; i < n; i += q)
37         {
38           if((i - 1) % p == 0) printf(" %d",i);
39           if((i + 1) % p == 0) printf(" %d",i + 1);
40         }
41         printf("\n");
42 
43     }
44     return 0;
45 }