2019银联高校极客挑战赛 复赛

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <string>
  6 #include <algorithm>
  7 #include <iostream>
  8 using namespace std;
  9 #define ll long long
 10 
 11 const double eps=1e-8;
 12 const ll inf=1e9;
 13 const ll mod=1e9+7;
 14 const int maxn=1e5+10;
 15 
 16 ///2,3,5,7,11,13
 17 
 18 struct node
 19 {
 20     ll g;
 21     ///large to small
 22     ll a[10],b[10];
 23 }f[maxn];
 24 
 25 ll zhi[maxn],zhi_cnt,maxv=1e5;
 26 ll x[300],gx[300],y[130][maxn];
 27 bool vis[maxn],use[maxn];
 28 ll p;
 29 
 30 ///10^5*64
 31 void dfs(ll i,ll j,ll k)
 32 {
 33     if (k==f[p].g+1)
 34     {
 35         ll l,z;
 36         y[j][0]=0;
 37         x[j]=i;
 38         z=f[p].g;
 39         for (l=1;l<=i;l++)
 40         {
 41             for (k=1;k<=z;k++)
 42                 if (l%zhi[f[p].a[k]]==0 && use[k])
 43                     break;
 44             if (k==z+1)
 45                 y[j][l]=y[j][l-1]+1;
 46             else
 47                 y[j][l]=y[j][l-1];
 48         }
 49         gx[j]=y[j][i];
 50         return;
 51     }
 52     use[k]=0;
 53     dfs(i,j*2,k+1);
 54     use[k]=1;
 55     dfs(i*zhi[f[p].a[k]],j*2+1,k+1);
 56 }
 57 
 58 ll work(ll u,ll v)
 59 {
 60     ll r=0,i,j;
 61     v/=u;
 62 
 63     i=1,j=1;
 64     while (i<=f[u].g && j<=f[p].g)
 65     {
 66         if (f[u].a[i]==f[p].a[j])
 67         {
 68             if (f[u].b[i]==f[p].b[j])
 69                 r=r*2;
 70             else
 71                 r=r*2+1;
 72             i++;
 73             j++;
 74         }
 75         else if (f[u].a[i]>f[p].a[j])
 76             i++;
 77         else
 78         {
 79             j++;
 80             r=r*2+1;
 81         }
 82     }
 83     while (j<=f[p].g)
 84         r=r*2+1,j++;
 85 
 86     return v/x[r]*gx[r]+y[r][v%x[r]];
 87 }
 88 
 89 int main()
 90 {
 91     ll t,i,j,k,maxv=1e5;
 92     ll n,m,sum;
 93     for (i=2;i<=maxv;i++)
 94     {
 95         if (!vis[i])
 96         {
 97             zhi[++zhi_cnt]=i;
 98             f[i].g=1;
 99             f[i].a[1]=zhi_cnt;
100             f[i].b[1]=1;
101         }
102         for (j=1;j<=zhi_cnt;j++)
103         {
104             k=i*zhi[j];
105             if (k>maxv)
106                 break;
107             vis[k]=1;
108             f[k]=f[i];
109             if (f[i].a[f[i].g]==j)
110                 f[k].b[f[k].g]++;
111             else
112             {
113                 f[k].g++;
114                 f[k].a[f[k].g]=j;
115                 f[k].b[f[k].g]=1;
116             }
117             if (i%zhi[j]==0)
118                 break;
119         }
120     }
121 
122     scanf("%lld",&t);
123     while (t--)
124     {
125         scanf("%lld%lld%lld",&n,&m,&p);
126 //        if (p==1)
127 //        {
128 //            printf("%lld\n",n*m);
129 //            continue;
130 //        }
131         dfs(1,0,1);
132 
133         sum=0;
134         for (i=1;i<=p;i++)
135             if (p%i==0)
136             {
137                 j=p/i;
138 
139                 sum+=work(i,n)*(m/j);
140             }
141         printf("%lld\n",sum);
142     }
143     return 0;
144 }
145 /*
146 5
147 1000000000 1000000000 1
148 1000000000 1000000000 2
149 1000000000 1000000000 10
150 100000000 100000000 2
151 10 20 15
152 1000000000 1000000000 30030
153 100000000 100000000 30030
154 
155 1
156 9 9 9
157 1
158 6 6 12
159 
160 1
161 20 20 11
162 
163 1
164 10 10 6
165 */