福州大学acm_福州大学acm题库

昨天在福州大学acm，a了几道题，很类似，有几道，都是用指数模算法，性能超好。

1586题Ones again，求1的位数

#include <iostream>

using namespace std;

long js(long a, long e, long n)
{
 long re = 1;

 while(e != 0)
 {
  if(e % 2 == 0)
  {
   a = (a*a) % n;
   e = e/2;
  }
  else
  {
   re = (a*re) % n;
   e = e-1;
  }
 }

 return re;
}

void ddd()
{
 long t;

 while(cin >> t)
 {
  long sum = 0;
  long i;
  for(i = 1; ; ++i)
  {
   sum += js(10, i-1, t);
   sum %= t;
   if(sum == 0)
   {
    cout << i << endl;
    break;
   }
  }
 }
}
  
int main()
{
 ddd();
 return 0;
} 

1584题Sparse Big Integer

#include <iostream>

using namespace std;

long js(long a, long e, long n)
{
 long re = 1;

 while(e != 0)
 {
  if(e % 2 == 0)
  {
   a = (a*a) % n;
   e = e/2;
  }
  else
  {
   re = (a*re) % n;
   e = e-1;
  }
 }

 return re;
}

void caa()
{
 int t;
 cin >> t;

 while(t--)
 {
  long k, n, sum = 0;
  long ak[11][2];
  cin >> k;

  int i;
  for(i = 0; i < k; i++)
  {
   cin >> ak[i][0] >> ak[i][1];
  }

  cin >> n;

  for(i = 0; i < k; ++i)
  {
   sum += (ak[i][0]*js(10, ak[i][1]-1, n)) % n;
  }

  cout << sum % n << endl;
 }
}

int main()

{

caa();

return 0;

}