codeforce 1474B Different Divisors 模拟 素数筛 C

**------------恢复内容开始------------**

codeforce 1474B Different Divisors 模拟 素数筛 C B. Different Divisors time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Positive integer x">xx is called divisor of positive integer y">yy, if y">yy is divisible by x">xx without remainder. For example, 1">11 is a divisor of 7">77 and 3">33 is not divisor of 8">88.

We gave you an integer d">dd and asked you to find the smallest positive integer a">aa, such that

  • a">aa has at least 4">44 divisors;
  • difference between any two divisors of a">aa is at least d">dd.
Input

The first line contains a single integer t">tt (1≤t≤3000">1≤t≤30001≤t≤3000) — the number of test cases.

The first line of each test case contains a single integer d">dd (1≤d≤10000">1≤d≤100001≤d≤10000).

Output

For each test case print one integer a">aa — the answer for this test case.

Example input Copy 
2
1
2
output Copy 
6
15
Note

In the first test case, integer 6">66 have following divisors: [1,2,3,6]">[1,2,3,6][1,2,3,6]. There are 4">44 of them and the difference between any two of them is at least 1">11. There is no smaller integer with at least 4">44 divisors.

In the second test case, integer 15">1515 have following divisors: [1,3,5,15]">[1,3,5,15][1,3,5,15]. There are 4">44 of them and the difference between any two of them is at least 2">22.

The answer 12">1212 is INVALID because divisors are [1,2,3,4,6,12]">[1,2,3,4,6,12][1,2,3,4,6,12]. And the difference between, for example, divisors 2">22 and 3">33 is less than d=2">d=2d=2.

b=001011">a=101110">d=102121">d">分析

要求两个因子之间至少差d，至少四个，最好是素数

那数据1e4。也不大，打表素数，挨个寻找，找到两个就可以了。

b=001011">a=101110">d=102121">d">代码

 https://codeforces.com/contest/1474/submission/105586801

#include 
#include 
#include 
#include 
#include 
#include <string.h>
#include 
#include 
#include <string>
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include <string.h>
#include 
#define sf scanf
#define pf printf
#define lf double
#define p123 printf("123\n");
#define pn printf("\n");
#define pk printf(" ");
#define p(n) printf("%d",n);
#define pln(n) printf("%d\n",n);
#define s(n) scanf("%d",&n);
#define ss(n) scanf("%s",n);
#define ps(n) printf("%s",n);
#define sld(n) scanf("%lld",&n);
#define pld(n) printf("%lld",n);
#define slf(n) scanf("%lf",&n);
#define plf(n) printf("%lf",n);
#define sc(n) scanf("%c",&n);
#define pc(n) printf("%c",n);
#define gc getchar();
#define ll long long
#define re(n,a) memset(n,a,sizeof(n));
#define len(a) strlen(a)
#define eps 1e-13
#define zero(x) (((x) > 0? (x):(-x)) < eps)
using namespace std;
int a[40000];
int main(){
    int t;
    s(t)
    int maxi = 30505;
    for(int i = 0; i <= maxi; i ++){
        a[i] = 1;
    }
    for(int i = 2; i <= maxi; i ++){
        if(a[i] == 1){
            for(int j = i*i; j <= maxi; j += i){
                a[j] = 0;
            }
        }
    }
    while(t --){
        int n;
        s(n)
        int x,y;
        for(int i = 1+n; i <= maxi; i ++){
            if(a[i] == 1){
                x = i;
                break;
            }
        }
        for(int i = x+n; i <= maxi; i ++){
            if(a[i] == 1){
                y = i;
                break;
            }
        }
        p(x*y) pn
    }
    return 0;
}
ACM

相关

acm讲解

「acmhdu - 6314」Matrix

第十三届河南省ACM-ICPC游记

ACM模板

Hyperf 接入阿里云ACM应用配置管理中心

[ACM] BFS & 双端BFS & A* & 双边BFS

计算几何 / Geometry（ACM-Template 2.0）

ACM入门方式

Linux 下使用 acme.sh 配置 Let's Encrypt 免费 SSL 证书 + 通配符证书

如何写好一篇高质量的IEEE/ACM Transaction级别的计算机科学论文?

ACM- java在acm中的快速读入，多组读入，快速输出模板

ACM - 动态规划 - P1282 多米诺骨牌

标签