結果
| 問題 |
No.2218 Multiple LIS
|
| コンテスト | |
| ユーザー |
 Asahi
|
| 提出日時 | 2023-02-17 22:05:17 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,675 bytes |
| コンパイル時間 | 3,527 ms |
| コンパイル使用メモリ | 85,216 KB |
| 実行使用メモリ | 56,108 KB |
| 最終ジャッジ日時 | 2024-07-19 13:16:59 |
| 合計ジャッジ時間 | 19,550 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 5 WA * 34 |
ソースコード
import java.util.*;
import java.io.*;
import java.math.*;
import java.util.regex.Pattern;
class Main{
static void solve(){
/*
* いちばんおおいそいんすうをみつけてそうさする
*/
int n = ni();
int [] A = IntArray(n);
int [] count = new int[1000000];
int max = 1;
int base = 1;
for(int i=0;i<n;i++) {
Map<Integer,Integer> pr = prime_factorization(A[i]);
for(int v : pr.keySet()) count[v]++;
}
for(int i=0;i<1000000;i++) {
if(max < count[i]){
max = count[i];
base = i;
}
}
int chain = 0;
for(int i=0;i<n;i++) {
if(A[i] % base == 0) break;
if(A[i] == 1) chain++;
}
output.print(chain+max);
}
/* 関数 */
static Map<Integer,Integer> prime_factorization(int val) {
Map<Integer,Integer> map = new HashMap<>();
for(int i=2; i*i<=val;i++) {
int count = 0;
while(val % i == 0) {
val /= i;
count++;
}
if(count > 0) map.put(i,count);
}
if(val != 1) map.put(val,1);
return map;
}
/* 定数 */
static PrintWriter output;
static Scanner sc;
static int Inf = 1010101010;
static long Lnf = (long)1e18;
static final long mod = 1000000007;
static final long MOD = 998244353 ;
/* タイポ誘発関数 */
static String cut(String S , int start, int end) { return S.substring(start,end);}
static char cut(String S , int start) { return S.charAt(start);}
static String tos(int val) { return Integer.toString(val);}
static String tos(long val) { return Long.toString(val);}
static int toi(String S) { return Integer.parseInt(S);}
static long tol(String S) { return Long.parseLong(S);}
/* 実装が面倒なやつ */
static boolean kaibun(String S) {
StringBuilder s = new StringBuilder();
s.append(S);
return s.reverse().toString().equals(S);
}
static boolean isNumber(String value) {
boolean result = false;
if (value != null) {
Pattern pattern = Pattern.compile("^[0-9]+$|-[0-9]+$");
result = pattern.matcher(value).matches();
}
return result;
}
static Map<Integer,Integer> counter(int [] A) {
HashMap<Integer,Integer> count = new HashMap<>();
for(int i=0;i<A.length;i++) {
if(!count.containsKey(A[i])) count.put(A[i],1);
else count.put(A[i],count.get(A[i])+1);
}
return count;
}
static Map<Long,Integer> counter(long [] A) {
HashMap<Long,Integer> count = new HashMap<>();
for(int i=0;i<A.length;i++) {
if(!count.containsKey(A[i])) count.put(A[i],1);
else count.put(A[i],count.get(A[i])+1);
}
return count;
}
/*入出力端折るやつ*/
static int ni(){ return Integer.parseInt(sc.next());}
static long nl(){ return Long.parseLong(sc.next());}
static double nd(){ return Double.parseDouble(sc.next());}
static String ns(){ return sc.next();}
static BigInteger bi(){ return sc.nextBigInteger();}
static BigDecimal bd(){ return sc.nextBigDecimal();}
static int [] IntArray(int n) {
int [] Array = new int[n];
for(int i=0;i<n;i++) Array[i] = ni();
return Array;
}
static int [][] IntArray(int n , int m) {
int [][] Array = new int[n][m];
for(int i=0;i<n;i++) for(int j=0;j<m;j++) Array[i][j] = ni();
return Array;
}
static long [] LongArray(int n) {
long [] Array = new long[n];
for(int i=0;i<n;i++) Array[i] = nl();
return Array;
}
static long [][] LongArray(int n , int m) {
long [][] Array = new long[n][m];
for(int i=0;i<n;i++) for(int j=0;j<m;j++) Array[i][j] = nl();
return Array;
}
static double [] DoubleArray(int n) {
double [] Array = new double[n];
for(int i=0;i<n;i++) Array[i] = nd();
return Array;
}
static double [][] DoubleArray(int n , int m) {
double [][] Array = new double[n][m];
for(int i=0;i<n;i++) for(int j=0;j<m;j++) Array[i][j] = nd();
return Array;
}
static String [] StringArray(int n) {
String [] Array = new String[n];
for(int i=0;i<n;i++) Array[i] = ns();
return Array;
}
static String [][] StringArray(int n , int m) {
String [][] Array = new String[n][m];
for(int i=0;i<n;i++) for(int j=0;j<m;j++) Array[i][j] = ns();
return Array;
}
static char [] CharArray(int n) {
char [] Array = new char[n];
String S = ns();
for(int i=0;i<n;i++) Array[i] = S.charAt(i);
return Array;
}
static char [][] CharArray(int n,int m) {
char [][] Array = new char[n][m];
for(int i=0;i<n;i++) {
String S = ns();
for(int j=0;j<m;j++) Array[i][j] = S.charAt(j);
}
return Array;
}
static void PrintArray(int [] A) {
for(int i=0;i<A.length;i++) output.print(A[i]+" ");
output.println();
}
static void PrintArray(long [] A) {
for(int i=0;i<A.length;i++) output.print(A[i]+" ");
output.println();
}
static void PrintArray(double [] A) {
for(int i=0;i<A.length;i++) output.print(A[i]+" ");
output.println();
}
static void PrintArray(boolean [] A) {
for(int i=0;i<A.length;i++) output.print(A[i]+" ");
output.println();
}
static void PrintArray(int [][] A) {
for(int i=0;i<A.length;i++) {
for(int j=0;j<A[i].length;j++) {
if(A[i][j] == Inf) output.print("X ");
else output.print(A[i][j]+" ");
}
output.println();
}
}
static void PrintArray(long [][] A) {
for(int i=0;i<A.length;i++) {
for(int j=0;j<A[i].length;j++) {
if(A[i][j] == Lnf) output.print("X ");
else output.print(A[i][j]+" ");
}
output.println();
}
}
static void PrintArray(boolean [][] A) {
for(int i=0;i<A.length;i++) {
for(int j=0;j<A[i].length;j++) {
output.print(A[i][j]?"O":"X");
}
output.println();
}
}
public static void main(String[] args){
output = new PrintWriter(System.out);
sc = new Scanner(System.in);
solve();
output.flush();
}
}