题意:https://codeforces.com/group/ikIh7rsWAl/contest/254825/problem/E
给你一个n,计算n / Sigma(1~n)的d(是n的只出现一次的因数)。
思路:
反正就是打表找规律,3组数据也能找规律,你们是真的nb嗷。
import java.math.BigInteger;
import java.util.Scanner; public class Main{
public static void main(String[] args){
Scanner cin=new Scanner(System.in); int T=cin.nextInt();
BigInteger n1=new BigInteger("1");
BigInteger n2=new BigInteger("2");
BigInteger n3=new BigInteger("3");
BigInteger n4=new BigInteger("4");
BigInteger n5=new BigInteger("5");
BigInteger n6=new BigInteger("6");
BigInteger a[]=new BigInteger[104];
a[1]=new BigInteger("2");
a[2]=new BigInteger("3");
a[3]=new BigInteger("5");
a[4]=new BigInteger("7");
a[5]=new BigInteger("11");
a[6]=new BigInteger("13");
a[7]=new BigInteger("17");
a[8]=new BigInteger("19");
a[9]=new BigInteger("23");
a[10]=new BigInteger("29");
a[11]=new BigInteger("31");
a[12]=new BigInteger("37");
a[13]=new BigInteger("41");
a[14]=new BigInteger("43");
a[15]=new BigInteger("47");
a[16]=new BigInteger("53");
a[17]=new BigInteger("59");
a[18]=new BigInteger("61");
a[19]=new BigInteger("67");
a[20]=new BigInteger("71");
a[21]=new BigInteger("73");
a[22]=new BigInteger("79");
a[23]=new BigInteger("83");
a[24]=new BigInteger("89");
a[25]=new BigInteger("97");
a[26]=new BigInteger("101");
a[27]=new BigInteger("103");
a[28]=new BigInteger("107");
a[29]=new BigInteger("109");
a[30]=new BigInteger("113");
a[31]=new BigInteger("127");
a[32]=new BigInteger("131");
a[33]=new BigInteger("137");
a[34]=new BigInteger("139");
a[35]=new BigInteger("149");
a[36]=new BigInteger("151");
a[37]=new BigInteger("157");
a[38]=new BigInteger("163");
a[39]=new BigInteger("167");
a[40]=new BigInteger("173");
a[41]=new BigInteger("179");
a[42]=new BigInteger("181");
a[43]=new BigInteger("191");
a[44]=new BigInteger("193");
a[45]=new BigInteger("197");
a[46]=new BigInteger("199");
a[47]=new BigInteger("211");
a[48]=new BigInteger("223");
a[49]=new BigInteger("227");
a[50]=new BigInteger("229");
a[51]=new BigInteger("233");
a[52]=new BigInteger("239");
a[53]=new BigInteger("241");
a[54]=new BigInteger("251");
a[55]=new BigInteger("257");
a[56]=new BigInteger("263");
a[57]=new BigInteger("269");
a[58]=new BigInteger("271");
a[59]=new BigInteger("277");
a[60]=new BigInteger("281");
a[61]=new BigInteger("283");
a[62]=new BigInteger("293");
a[63]=new BigInteger("307");
a[64]=new BigInteger("311");
a[65]=new BigInteger("313");
a[66]=new BigInteger("317");
a[67]=new BigInteger("331");
a[68]=new BigInteger("337");
a[69]=new BigInteger("347");
a[70]=new BigInteger("349");
a[71]=new BigInteger("353");
a[72]=new BigInteger("359");
a[73]=new BigInteger("367");
a[74]=new BigInteger("373");
a[75]=new BigInteger("379");
a[76]=new BigInteger("383");
a[77]=new BigInteger("389");
a[78]=new BigInteger("397");
a[79]=new BigInteger("401");
a[80]=new BigInteger("409");
a[81]=new BigInteger("419");
a[82]=new BigInteger("421");
a[83]=new BigInteger("431");
a[84]=new BigInteger("433");
a[85]=new BigInteger("439");
a[86]=new BigInteger("443");
a[87]=new BigInteger("449");
a[88]=new BigInteger("457");
a[89]=new BigInteger("461");
a[90]=new BigInteger("463");
a[91]=new BigInteger("467");
a[92]=new BigInteger("479");
a[93]=new BigInteger("487");
a[94]=new BigInteger("491");
a[95]=new BigInteger("499");
a[96]=new BigInteger("503");
a[97]=new BigInteger("509");
a[98]=new BigInteger("521");
a[99]=new BigInteger("523");
a[100]=new BigInteger("541"); for(int i=1;i<=T;++i){
BigInteger N=cin.nextBigInteger();
int flag=N.compareTo(n6);
int cnt=0;
BigInteger A=new BigInteger("1");
BigInteger B=new BigInteger("2");
if(flag==1){
BigInteger start=new BigInteger("6");
int P=3;
for(int j=1;j<=10000;j++) {
start=start.multiply(a[P]);
if(start.compareTo(N)==1)
break;
else {
cnt++;
P++;
}
}
int PP=3;
for(int j=1;j<=cnt;j++) {
BigInteger up=a[PP];
BigInteger ttt=a[PP];
ttt=ttt.add(n1);
BigInteger down=ttt;
A=A.multiply(up);
B=B.multiply(down);
PP++;
}
BigInteger gcd=A.gcd(B);
A=A.divide(gcd);
B=B.divide(gcd);
System.out.println(A+"/"+B);
}
else{
if(N.compareTo(n1)==0)
System.out.println("1/1");
else if(N.compareTo(n2)==0)
System.out.println("2/3");
else if(N.compareTo(n3)==0)
System.out.println("2/3");
else if(N.compareTo(n4)==0)
System.out.println("2/3");
else if(N.compareTo(n5)==0)
System.out.println("2/3");
else if(N.compareTo(n6)==0)
System.out.println("1/2");
}
}
}
}