首页 > 代码库 > XVII Open Cup named after E.V. Pankratiev Stage 14, Grand Prix of Tatarstan, Sunday, April 2, 2017 Problem A. Arithmetic Derivative

XVII Open Cup named after E.V. Pankratiev Stage 14, Grand Prix of Tatarstan, Sunday, April 2, 2017 Problem A. Arithmetic Derivative

2024-11-18 18:38:02   202人阅读

题目：Problem A. Arithmetic Derivative
Input file: standard input
Output file: standard input
Time limit: 1 second
Memory limit: 256 mebibytes
Lets define an arithmetic derivative:
? if p = 1 then p0 = 0;
? if p is prime then p0 = 1;
? if p is not prime then n0 = (a · b)0 = a0 · b + a · b0.
For example, 60 = (2 · 3)0 = 20 · 3 + 2 · 30 = 5.
Given positive integers k and r, find all positive integers n such as n ≤ r and n0 = k · n.
Input
Input contains two integers k and r (1 ≤ k ≤ 30; 1 ≤ r ≤ 2 · 1018).
Output
If there are no such numbers, print 0. Otherwise in first line print m — number of positive integers n does
not exceeding r, for which n0 = k · n. Second line then must contain those m integers in ascending order.
Examples

standard input standard input
1 100 2
4 27
1 2 0 
 1 #include<iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 long long num[10]={0,4,27,3125,823543,285311670611,302875106592253};
 7 
 8 long long k,r,ans;
 9 
10 vector<long long> v;
11 
12 void dfs(int x,long long nownum,long long r)
13 {
14     if(x>6)
15     {
16         if(r)
17             return ;
18         if(nownum<=k)
19         {
20             ans++;
21             v.push_back(nownum);
22         }
23         return ;
24     }
25     long long nn=1;
26     for(int i=0;i<=r;i++)
27     {
28         if(i==0)
29             dfs(x+1,nownum,r);
30         else
31         {
32             if(k/nn<num[x])
33                 break;
34             else
35                 nn*=num[x];
36             if(k/nownum<nn)
37                 break;
38             dfs(x+1,nownum*nn,r-i);
39         }
40     }
41     return ;
42 }
43 
44 int main()
45 {
46     cin>>r>>k;
47     if(r==1)
48     {
49         for(int i=1;i<=6;i++)
50             if(num[i]<=k)
51                 ans++;
52         cout<<ans<<endl;
53         for(int i=1;i<=ans;i++)
54             cout<<num[i]<<‘ ‘;
55         return 0;
56     }
57     dfs(1,1,r);
58     cout<<ans<<endl;
59     sort(v.begin(),v.end());
60     for(int i=0;i<ans;i++)
61         cout<<v[i]<<‘ ‘;
62     return 0;
63 }

 

　　

 

XVII Open Cup named after E.V. Pankratiev Stage 14, Grand Prix of Tatarstan, Sunday, April 2, 2017 Problem A. Arithmetic Derivative


联系
我们