算法题

桃扇骨 2022-01-10 10:23 192阅读 0赞

<table> 
 <tbody> 
  <tr> 
   <td>N.RSA加密算法</td> 
  </tr> 
  <tr> 
   <td> 
    <table> 
     <tbody> 
      <tr> 
       <td>Time Limit: 1000 MS</td> 
       <td>Memory Limit: 32768 K</td> 
      </tr> 
     </tbody> 
    </table> 
    <table> 
     <tbody> 
      <tr> 
       <td>Total Submit: 45 <span>(15 users)</span></td> 
       <td>Total Accepted: 14 <span>(14 users)</span></td> 
       <td>Special Judge:&nbsp;<span>No</span></td> 
      </tr> 
     </tbody> 
    </table></td> 
  </tr> 
  <tr> 
   <td>Description</td> 
  </tr> 
  <tr> 
   <td> <p>鉴于电报加密系统的脆弱性，魔法学院发明了名为RSA的公钥加密算法，它能够抵抗目前为止已知的所有密码攻击，RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。</p> <p>请编程输入一个大于1的整数，打印出它的素数分解式。如输入75，则打印：75=3*5*5。</p> </td> 
  </tr> 
  <tr> 
   <td>Input</td> 
  </tr> 
  <tr> 
   <td> <p>有多组数据，第一行一个正整数t（t&lt;100）表示输入数据组数，接下来有t组输入数据，每组数据占1行，输入为一个整数n（n&lt;1000000)。</p> </td> 
  </tr> 
  <tr> 
   <td>Output</td> 
  </tr> 
  <tr> 
   <td> <p>对于每组输入，输出一个素数分解式，占一行，不包含多余空格。</p> <p>形如：x=p1*p2*p3*……*pn。</p> </td> 
  </tr> 
  <tr> 
   <td>Sample Input</td> 
  </tr> 
  <tr> 
   <td> <p>2</p> <p>2</p> <p>6</p> </td> 
  </tr> 
  <tr> 
   <td>Sample Output</td> 
  </tr> 
  <tr> 
   <td> <p>2=2</p> <p>6=2*3</p> </td> 
  </tr> 
  <tr> 
   <td>Hint</td> 
  </tr> 
  <tr> 
   <td> <p>素数分解式应按从小到大输出。</p> <p>例如：6=2*3而非6=3*2。</p> </td> 
  </tr> 
 </tbody> 
</table>

1 #include <stdio.h>
     2 #include <iostream>
     3 #include <math.h>
     4 using namespace std;
     5 int main() {
     6     int t;
     7     int n;
     8     cin>>t;
     9     while(t--) {
    10         cin>>n;
    11         int  cnt = 2;
    12         bool flag = true;
    13         cout<<n<<"=";
    14         while(n != 1){
    15             if(n%cnt == 0){
    16                if(flag){
    17                    cout<<cnt;
    18                    flag = false;
    19                }
    20                 else cout<<"*"<<cnt;
    21                 n = n/cnt;
    22                 cnt = 2;
    23             }
    24             else cnt++;
    25         }
    26         cout<<endl;
    27     }
    28 }

<table> 
 <tbody> 
  <tr> 
   <td>M.停电</td> 
  </tr> 
  <tr> 
   <td> 
    <table> 
     <tbody> 
      <tr> 
       <td>Time Limit: 1000 MS</td> 
       <td>Memory Limit: 32768 K</td> 
      </tr> 
     </tbody> 
    </table> 
    <table> 
     <tbody> 
      <tr> 
       <td>Total Submit: 60 <span>(17 users)</span></td> 
       <td>Total Accepted: 18 <span>(15 users)</span></td> 
       <td>Special Judge:&nbsp;<span>No</span></td> 
      </tr> 
     </tbody> 
    </table></td> 
  </tr> 
  <tr> 
   <td>Description</td> 
  </tr> 
  <tr> 
   <td> <p>由于修罗王的破坏，魔法世界的电力严重短缺，M个城市从城市1开始每隔N个城市轮流断电，求最小的N使最后断电的为第K号城市。若没有此方案则输出“No Solution!”</p> </td> 
  </tr> 
  <tr> 
   <td>Input</td> 
  </tr> 
  <tr> 
   <td> <p>有多组数据，第一行一个正整数t（t&lt;100）表示输入数据组数，接下来有t组输入数据，每组数据占1行，输入为用空格隔开的两个整数，M、K（2&lt;=K&lt;=M&lt;100）。</p> </td> 
  </tr> 
  <tr> 
   <td>Output</td> 
  </tr> 
  <tr> 
   <td> <p>对于每组输入，输出一个整数，表示N的值，占一行。</p> </td> 
  </tr> 
  <tr> 
   <td>Sample Input</td> 
  </tr> 
  <tr> 
   <td> <p>2</p> <p>2 2</p> <p>4 3</p> </td> 
  </tr> 
  <tr> 
   <td>Sample Output</td> 
  </tr> 
  <tr> 
   <td> <p>1</p> <p>No Solution!</p> </td> 
  </tr> 
  <tr> 
   <td>Hint</td> 
  </tr> 
  <tr> 
   <td> <p>已经断电的城市，下次不再计数。</p> <p>M个城市是环形排列，即：第M个城市的下一个为第一个城市。</p> <p>第一个断电的为N号城市！</p> </td> 
  </tr> 
 </tbody> 
</table>

1 #include <stdio.h>
     2 #include <iostream>
     3 #include <math.h>
     4 using namespace std;
     5 struct List {
     6     int num;
     7     List *next;
     8 };
     9 int main() {
    10     int t;
    11     int k, m, tmp;
    12     cin>>t;
    13     while(t--) {
    14         bool  flag = true;
    15         cin>>m>>k;
    16         for(int i = 1; i <= m; i++) {
    17             List *head,*p,*pre;
    18             head = new List;
    19             p = head;
    20             for(int i = 1; i <= m; i++) {
    21                 List *t = new List;
    22                 t->num = i;
    23                 t->next = NULL;
    24                 p->next = t;
    25                 p = t;
    26             }
    27             p->next = head->next;
    28             pre = head;
    29             p = head->next;
    30             tmp = m;
    31             while(tmp>1) {
    32                 for(int j = 0; j < i-1; j++ ) {
    33                     pre = p;
    34                     p = p->next;
    35                 }
    36                 pre->next = p->next;
    37                 List *d ;
    38                 d = p;
    39                 p = pre->next;
    40                 tmp--;
    41             }
    42             if(p->num == k) {cout<<i<<endl;flag = false;break;}
    43         }
    44         if(flag)
    45             cout<<"No Solution!"<<endl;
    46 
    47     }
    48 }

转载于:https://www.cnblogs.com/Lune-Qiu/p/7647846.html