-
-
Save meooow25/437093ca7895f28067f5abb1496ade4d to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.*; | |
import java.io.*; | |
class triangle_grid{ | |
static Vector<Integer>prime = new Vector<>(); | |
static boolean is_composite[]=new boolean[1000001]; | |
static long phi1[]=new long[1000001]; | |
static long phi2[]=new long[1000001]; | |
static int M=1000000007; | |
public static long power(long x, long y, long m) | |
{ | |
if (y == 0) | |
return 1; | |
long p = power(x, y / 2, m) % m; | |
p = (p * p) % m; | |
return (y % 2 == 0) ? p : (x * p) % m; | |
} | |
public static long sum(long n){ | |
long x=(long)n*(n+1)/2; | |
return x%M; | |
} | |
public static long mul(long a,long b,long c,long d) | |
{ | |
long ans=a; | |
ans=(ans*b)%M; | |
ans=(ans*c)%M; | |
ans=(ans*d)%M; | |
return ans; | |
} | |
public static void sieve (int n) { | |
for (int i = 2; i < n; ++i) { | |
if (!is_composite[i]) { | |
prime.add(i); | |
phi1[i] = i - 1; | |
phi2[i] =(long) i*i - 1; | |
} | |
for (int j = 0; j < prime.size () && (i*prime.get(j))<=n; ++j) { | |
is_composite[i * prime.get(j)] = true; | |
if (i % prime.get(j) == 0) { | |
phi1[i * prime.get(j)] = phi1[i] * prime.get(j); | |
phi2[i * prime.get(j)] = phi2[i] * prime.get(j)*prime.get(j); | |
break; | |
} else { | |
phi1[i * prime.get(j)] = phi1[i] * phi1[prime.get(j)]; | |
phi2[i * prime.get(j)] = phi2[i] * phi2[prime.get(j)]; | |
} | |
} | |
} | |
} | |
public static void main(String[] args)throws IOException { | |
Scanner in=new Scanner(System.in); | |
long n=in.nextInt(); | |
long m=in.nextInt(); | |
sieve((int)n); | |
int i,j; | |
phi1[1]=phi2[1]=1; | |
long x=n-1; | |
long y=m-1; | |
long p,q,count,sum1,sum2,c1,c2,c3,c4,num,den,mmif,ans; | |
count=sum1=sum2=c1=c2=c3=c4=num=den=0; | |
for(i=1;i<=x;i++) | |
{ | |
count=0; | |
p=x/i; | |
q=y/i; | |
count=(count+mul(n,m,p,q))%M; | |
count=(count-mul(n,i,p,sum(q))+M)%M; | |
count=(count-mul(i,m,sum(p),q)+M)%M; | |
count=(count+mul(i,i,sum(p),sum(q)))%M; | |
sum1=(sum1+(count*(phi1[i]%M))%M)%M; | |
sum2=(sum2+(count*(phi2[i]%M))%M)%M; | |
} | |
for(i=1;i<=x;i++) | |
{ | |
c1=(c1+((n-i)*i)%M)%M; | |
c3=(c3+mul((n-i),1,i,i))%M; | |
} | |
for(i=1;i<=y;i++) | |
{ | |
c2=(c2+((m-i)*i)%M)%M; | |
c4=(c4+mul((m-i),1,i,i))%M; | |
} | |
sum1=(sum1*4)%M; | |
sum1=(sum1+mul(2,1,m,c1))%M; | |
sum1=(sum1+mul(2,1,n,c2))%M; | |
sum2=(sum2*4)%M; | |
sum2=(sum2+mul(2,1,m,c3))%M; | |
sum2=(sum2+mul(2,1,n,c4))%M; | |
num=(num+mul(3,n,m,sum1))%M; | |
num=(num-mul(1,1,6,sum2)+M)%M; | |
x=(n*n)%M; | |
y=(m*m)%M; | |
den=(den+mul(n,m,x,y))%M; | |
den=(den-mul(3,1,1,sum1)+M)%M; | |
den=(den-mul(1,1,n,m)+M)%M; | |
mmif=power(den,M-2,M); | |
ans=(num*mmif)%M; | |
System.out.println(ans); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment