大发体育娱乐在线-大发体育娱乐官方网站-大发体育娱乐登录网址
做最好的网站

读书领会

来源:http://www.dfwstonefabricators.com 作者:关于计算机 人气:129 发布时间:2019-11-15
摘要:URAL 1083. Factorials!!! (阅读理解)   1204. Idempotents Time limit: 1.0 second Memory limit: 64 MB   The number x is called an idempotentmodulo n if x * x = x (mod n ) Write the program to find all idempotentsmodulo n , where n is

URAL 1083. Factorials!!! (阅读理解)

 

1204. Idempotents

Time limit: 1.0 second
Memory limit: 64 MB

 

The number x is called an idempotent modulo n if

x*x = x (mod n)

Write the program to find all idempotents modulo n, where n is a product of two distinct primes p and q.

1083. Factorials!!!

Time limit: 1.0 second
Memory limit: 64 MB
Definition 1. n!!…! = n(n?k)(n?2k)…(n mod k), if k doesn’t divide n; n!!…! = n(n?k)(n?2k)…k, if k divides n (There are k marks ! in the both cases). Definition 2.*X modY — a remainder after division of X by Y. For example, 10 mod 3 = 1; 3! = 3·2·1; 10!!! = 10·7·4·1. Given numbers n and k* we have calculated a value of the expression in the first definition. Can you do it as well?

Input

First line contains the number k of test cases to consider (1 ≤ k ≤ 1000). Each of the following k lines contains one number n < 109.

Input

contains the only line: one integer n, 1 ≤ n ≤ 10, then exactly one space, then k exclamation marks, 1 ≤ k ≤ 20.

Output

Write on the i-th line all idempotents of i-th test case in increasing order. Only nonnegative solutions bounded by n should be printed.

Output

contains one number — n!!…! (there are k marks ! here).

Sample

input output
3
6
15
910186311
0 1 3 4
0 1 6 10
0 1 303395437 606790875

Problem Author: Pavel Atnashev
Problem Source: USU Internal Contest, March 2002

大意:给出n, 求x, 使得x*x = x(mod n)

思路:x1 = 0, x2 = 1时公式成立

x*x = x (mod n)

n = q*p

x*(x-1) = (a*b)*(q*p) , a, b为整数

(1)x = a*q, x-1 = b*p,

a*q +b*p = x + (x-1) = 1;

用拓展欧几里得算法求出a, b, x3 = a*q;

(2) x-1 = a*q, x = b*p

x4 = b*p

  1 #include <iostream>
  2 #include <sstream>
  3 #include <fstream>
  4 #include <string>
  5 #include <vector>
  6 #include <deque>
  7 #include <queue>
  8 #include <stack>
  9 #include <set>
 10 #include <map>
 11 #include <algorithm>
 12 #include <functional>
 13 #include <utility>
 14 #include <bitset>
 15 #include <cmath>
 16 #include <cstdlib>
 17 #include <ctime>
 18 #include <cstdio>
 19 #include <cstring>
 20 #define FOR(i, a, b)  for(int i = (a); i <= (b); i++)
 21 #define RE(i, n) FOR(i, 1, n)
 22 #define FORP(i, a, b) for(int i = (a); i >= (b); i--)
 23 #define REP(i, n) for(int i = 0; i <(n); ++i)
 24 #define SZ(x) ((int)(x).size )
 25 #define ALL(x) (x).begin(), (x.end())
 26 #define MSET(a, x) memset(a, x, sizeof(a))
 27 using namespace std;
 28 
 29 
 30 typedef long long int ll;
 31 typedef pair<int, int> P;
 32 int read() {
 33     int x=0,f=1;
 34     char ch=getchar();
 35     while(ch<'0'||ch>'9') {
 36         if(ch=='-')f=-1;
 37         ch=getchar();
 38     }
 39     while(ch>='0'&&ch<='9') {
 40         x=x*10+ch-'0';
 41         ch=getchar();
 42     }
 43     return x*f;
 44 }
 45 const double pi=3.14159265358979323846264338327950288L;
 46 const double eps=1e-6;
 47 const int mod = 1e9 + 7;
 48 const int INF = 0x3f3f3f3f;
 49 const int MAXN = 100005;
 50 const int xi[] = {0, 0, 1, -1};
 51 const int yi[] = {1, -1, 0, 0};
 52 
 53 int N, T;
 54 int a[MAXN], prime[MAXN], cnt;
 55 void init() {
 56     cnt = 0;
 57     for(int i = 2; i < MAXN; i++) a[i] = true;
 58     for(int i = 2; i < MAXN; i++) {
 59         if(a[i]) {
 60             prime[++cnt] = i;
 61         }
 62         for(int j = 1; j <= cnt; j++) {
 63             if(i*prime[j] >= MAXN) break;
 64             a[i*prime[j]] = false;
 65             if(i%prime[j] == 0) break;
 66         }
 67     }
 68 }
 69 int exgcd(int a, int b, int &x, int &y) {
 70     int d = a;
 71     if(b != 0) {
 72         d = exgcd(b, a%b, y, x);
 73         y -= (a/b)*x;
 74     } else {
 75         x = 1, y = 0;
 76     }
 77     return d;
 78 }
 79 int main() {
 80     //freopen("in.txt", "r", stdin);
 81     init();
 82     int t, n;
 83     scanf("%d", &t);
 84     while(t--) {
 85         scanf("%d", &n);
 86         int p = - 1, q = -1;
 87         for(int i = 1; i <= cnt; i++) {
 88             if(n%prime[i] == 0) {
 89                 int k = n/prime[i];
 90                 int flag = 1;
 91                 for(int j = 2; j*j <= k; j++){
 92                     if(k%j == 0){
 93                         flag = 0;
 94                         break;
 95                     }
 96                 }
 97                 if(flag){
 98                     p = prime[i], q = n/prime[i];
 99                     break;
100                 }
101             }
102         }
103       //  printf("%d %dn", p, q);
104         //  if(p > q) swap(p, q);
105         int x, y, res1, res2, d;
106         d = exgcd(p, q, x, y);
107        // printf("%d %dn", x, y);
108         res1 = p*x;
109         if(res1 <= 0) res1 += n;
110       //  printf("%dn",res1);
111         d = exgcd(q, p, x, y);
112        // printf("%d %dn", x, y);
113         res2 = q*x;
114         if(res2 <= 0) res2 += n;
115         //printf("%dn", res2);
116         if(res2 < res1) swap(res1, res2);
117         printf("0 1 %d %dn", res1, res2);
118     }
119     return 0;
120 }

 

Sample

input output
9 !!
945

Problem Author: Oleg Katz
Problem Source: The 3rd high school children programming contest, USU, Yekaterinburg, Russia, March 4, 2001

 

 

 

 

 

解析:直接按题目中的定义计算即可。

 

 

 

 

AC代码:

 

#include 
using namespace std;

int main(){
    int n;
    string s;
    while(~scanf("%d", &n)){
        cin>>s;
        int k = s.size();
        int ans = 1;
        if(n % k){
            int t = n / k;
            for(int i=0; i<=t; i++){
                ans *= (n - i * k);
            }
        }
        else{
            int t = n / k - 1;
            for(int i=0; i<=t; i++){
                ans *= (n - i * k);
            }
        }
        printf("%dn", ans);
    }
    return 0;
}

 

1083. Factorials!!! (阅读理解) 1083. Factorials!!! Time limit: 1.0 second Memory limit: 64 MB Definition 1. n !!! = n ( n ? k )( n ?2 k )( n mod k ), if k doesnt divid...

本文由大发体育娱乐在线发布于关于计算机,转载请注明出处:读书领会

关键词:

频道精选

最火资讯