会不会是没开long long的原因
by zhouzihang1 @ 2023-08-02 21:47:50
@[zhouzihang1](/user/827018)
还是40分~~~
```cpp
#include<bits/stdc++.h>
using namespace std;
long long N, m1, m2, s[10005];
struct factor
{
long long index[205], base[205], sum;
}M, S[10005];
void doit( long long num, long long t, bool flag, long long id )
{
long long idx = 0;
for( long long i = 2; i <= num / i; i++ )
{
if( num % i == 0 )
{
int cnt = 0;
while( num % i == 0 )
cnt++, num /= i;
if( !flag )
M.base[++idx] = i, M.index[idx] = cnt * t;
else
S[id].base[++idx] = i, S[id].index[idx] = cnt * t;
}
}
if( num > 1 )
{
if( !flag )
M.base[++idx] = num, M.index[idx] = t;
else
S[id].base[++idx] = num, S[id].index[idx] = t;
}
if( !flag )
M.sum = idx;
else
S[id].sum = idx;
return;
}
long long f( long long a, long long b )
{
return (long long)ceil( log2( b * 1.0 / a ) ) + 1;
}
long long cal( long long id )
{
for( int i = 1; i <= M.sum; i++ )
{
int idx = lower_bound( S[id].base + 1, S[id].base + S[id].sum + 1, M.base[i] ) - S[id].base;
if( S[id].base[idx] != M.base[i] )
return -1;
}
long long ans = 0;
for( int i = 1; i <= M.sum; i++ )
{
int idx = lower_bound( S[id].base + 1, S[id].base + S[id].sum + 1, M.base[i] ) - S[id].base;
ans = max( ans, f( S[id].index[idx], M.index[i] ) );
}
return ans;
}
int main()
{
scanf( "%lld%lld%lld", &N, &m1, &m2 );
for( int i = 1; i <= N; i++ )
scanf( "%lld", &s[i] );
if( m1 == 1 )
{
printf( "%lld", 0 );
return 0;
}
doit( m1, m2, 0, 0 );
for( int i = 1; i <= N; i++ )
doit( s[i], 1, 1, i );
long long minstep = LONG_LONG_MAX;
for( int i = 1; i <= N; i++ )
{
long long x = cal(i);
if( x == -1 )
continue;
minstep = min( minstep, x );
}
printf( "%lld", minstep == LONG_LONG_MAX ? -1 : minstep );
return 0;
}
by liuzhuoxin @ 2023-08-03 21:09:13
@[liuzhuoxin](/user/768712) 把开longlong那个代码的f函数改一下就行了
by YuhongZhou @ 2024-02-04 14:15:27
```cpp
#include<bits/stdc++.h>
using namespace std;
long long N, m1, m2, s[10005];
struct factor
{
long long index[205], base[205], sum;
}M, S[10005];
void doit( long long num, long long t, bool flag, long long id )
{
long long idx = 0;
for( long long i = 2; i <= num / i; i++ )
{
if( num % i == 0 )
{
int cnt = 0;
while( num % i == 0 )
cnt++, num /= i;
if( !flag )
M.base[++idx] = i, M.index[idx] = cnt * t;
else
S[id].base[++idx] = i, S[id].index[idx] = cnt * t;
}
}
if( num > 1 )
{
if( !flag )
M.base[++idx] = num, M.index[idx] = t;
else
S[id].base[++idx] = num, S[id].index[idx] = t;
}
if( !flag )
M.sum = idx;
else
S[id].sum = idx;
return;
}
long long f( long long a, long long b )
{
return (long long)ceil(( b * 1.0 / a ));
}
long long cal( long long id )
{
for( int i = 1; i <= M.sum; i++ )
{
int idx = lower_bound( S[id].base + 1, S[id].base + S[id].sum + 1, M.base[i] ) - S[id].base;
if( S[id].base[idx] != M.base[i] )
return -1;
}
long long ans = 0;
for( int i = 1; i <= M.sum; i++ )
{
int idx = lower_bound( S[id].base + 1, S[id].base + S[id].sum + 1, M.base[i] ) - S[id].base;
ans = max( ans, f( S[id].index[idx], M.index[i] ) );
}
return ans;
}
int main()
{
scanf( "%lld%lld%lld", &N, &m1, &m2 );
for( int i = 1; i <= N; i++ )
scanf( "%lld", &s[i] );
if( m1 == 1 )
{
printf( "%lld", 0 );
return 0;
}
doit( m1, m2, 0, 0 );
for( int i = 1; i <= N; i++ )
doit( s[i], 1, 1, i );
long long minstep = LONG_LONG_MAX;
for( int i = 1; i <= N; i++ )
{
long long x = cal(i);
if( x == -1 )
continue;
minstep = min( minstep, x );
}
printf( "%lld", minstep == LONG_LONG_MAX ? -1 : minstep );
return 0;
}
```
by YuhongZhou @ 2024-02-04 14:17:09